A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs
---
paper_title: Traversability and connectivity of the middle graph of a graph

paper_content:

We define a graph M(G) as an intersection graph @W(F) on the point set V(G) of any graph G. Let X(G) be the line set of G and F = V'(G) @? X(G), where V'(G) indicates the family of all one point subsets of the set V(G). Let M(G) = @W(F). M(G) is called the middle graph of G. The following theorems result: 1.Theorem 1. Let G be any graph and G^+ be a graph constructed from G. Then we have L(G^+)@?M(G), where L(G^+) is the line graphof G^+ 2.Theorem 2. Let G be a graph. The middle graph M(G) of G is hamiltonian if and only if G contains a closed spanning trail. 3.Theorem 3. If a graph G is eulerian, then the middle graph m(G) of G is eulerian and hamiltonian. 4.Theorem 4. If M(G) is eulerian, then G is eulerian and M(G) is hamiltonian. 5.Theorem 5. Let G be a graph. The middle graph M(G) of G contains a closed spanning trail if and only if G is connected and without points of degree =< 1. 6.Theorem 6. If a graph G is n-line connected, then the middle graph M(G) is n-connected.
---
paper_title: Bound graphs of a partially ordered set

paper_content:

A device for intermittently tensioning a yarn passing therethrough in which a motor cam acts on a tension train mounted on a fixed shaft. The tension train is composed of a tension adjuster which provides tension on a base plate, spring, and tension discs mounted between a stop and the tension adjuster. In an embodiment of the invention a method for intermittently tensioning a yarn by passing the yarn between the tension discs of the device described above.
---
paper_title: Food webs competition graphs and the boxicity of ecological phase space

paper_content:

Two species in an ecosystem compete if and only if they have intersecting ecological niches. Competition can be defined independently by using a food web for the ecosystem, and this notion of competition gives rise to a competition graph. This paper briefly describes the problem of representing the competition graph as an intersection graph of boxes (k-dimensional rectangles representing ecological niches) in Euclidean k-space and then discusses the class of graphs which arise as competition graphs of (acyclic) food webs.
---
paper_title: WELL-COVERED GRAPHS: A SURVEY

paper_content:

Abstract A graph G is well-covered (or w-c) if every maximal independent set of points in G is also maximum. Clearly, this is equivalent to the property that the greedy algorithm for constructing a maximal independent set always results in a maximum independent set. Although the problem of independence number is well-known to be NP-complete, it is trivially polynomial for well-covered graphs. The concept of well-coveredness was introduced by the author in [P1] and was first discussed therein with respect to its relationship to a number of other properties involving the independence number. Since then, a number of results about well-covered graphs have been obtained. It is our purpose in this paper to survey these results for the first time. As the reader will see, many of the results we will discuss are quite recent and have not as yet appeared in print.
---
paper_title: Total Graphs and Traversability

paper_content:

With every graph G (finite and undirected with no loops or multiple lines) there is associated a graph L ( G ), called the line-graph of G , whose points correspond in a one-to-one manner with the lines of G in such a way that two points of L ( G ) are adjacent if and only if the corresponding lines of G are adjacent. This concept was originated by Whitney ( 3 ). In a similar way one can associate with G another graph which we call its total graph and denote by T ( G ). This new graph has the property that a one-to-one correspondence can be established between its points and the elements (the set of points and lines) of G such that two points of T ( G ) are adjacent if and only if the corresponding elements of G are adjacent (if both elements are points or both are lines) or theyare incident
---
paper_title: Traversability and connectivity of the middle graph of a graph

paper_content:

We define a graph M(G) as an intersection graph @W(F) on the point set V(G) of any graph G. Let X(G) be the line set of G and F = V'(G) @? X(G), where V'(G) indicates the family of all one point subsets of the set V(G). Let M(G) = @W(F). M(G) is called the middle graph of G. The following theorems result: 1.Theorem 1. Let G be any graph and G^+ be a graph constructed from G. Then we have L(G^+)@?M(G), where L(G^+) is the line graphof G^+ 2.Theorem 2. Let G be a graph. The middle graph M(G) of G is hamiltonian if and only if G contains a closed spanning trail. 3.Theorem 3. If a graph G is eulerian, then the middle graph m(G) of G is eulerian and hamiltonian. 4.Theorem 4. If M(G) is eulerian, then G is eulerian and M(G) is hamiltonian. 5.Theorem 5. Let G be a graph. The middle graph M(G) of G contains a closed spanning trail if and only if G is connected and without points of degree =< 1. 6.Theorem 6. If a graph G is n-line connected, then the middle graph M(G) is n-connected.
---
paper_title: Algorithmic graph theory and perfect graphs

paper_content:

Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to the field. This new Annals edition continues to convey the message that intersection graph models are a necessary and important tool for solving real-world problems. It remains a stepping stone from which the reader may embark on one of many fascinating research trails. The past twenty years have been an amazingly fruitful period of research in algorithmic graph theory and structured families of graphs. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. These have lead to new families of perfect graphs and many algorithmic results. These are surveyed in the new Epilogue chapter in this second edition. New edition of the "Classic" book on the topic Wonderful introduction to a rich research area Leading author in the field of algorithmic graph theory Beautifully written for the new mathematician or computer scientist Comprehensive treatment
---
paper_title: Trivially perfect graphs

paper_content:

An undirected graph is trivially perfect if for every induced subgraph the stability number equals the number of (maximal) cliques. We characterize the trivially perfect graphs as a proper subclass of the triangulated graphs (thus disproving a claim of Buneman 3), and we relate them to some well-known classes of perfect graphs.
---
paper_title: An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph

paper_content:

Given a graph H with E edges and N nodes, a graph G is sought such that H is the line graph of G , if G exists. The algorithm does this within the order of E steps, in fact in E + O ( N ) steps. This algorithm is optimal in its complexity.
---
paper_title: The general maximum matching algorithm of micali and vazirani

paper_content:

We give a clear exposition of the algorithm of Micali and Vazirani for computing a maximum matching in a general graph. This is the most efficient algorithm known for general matching. On a graph withn vertices andm edges this algorithm runs inO(n1/2m) time.
---
paper_title: NP-completeness of edge-colouring some restricted graphs

paper_content:

Abstract The problem of determining the chromatic index of a regular graph of fixed degree r ≥ 3 is known to be NP-complete. We show that several other restricted versions of the problem are NP-complete. We show that the chromatic index problem restricted to regular comparability graphs of degree r ≥ 3, perfect graphs, regular line graphs of odd degree r ≥ 3, and claw-free graphs remains NP-complete, and thus resolve four open problems in Johnson's “The NP-completeness Column: an Ongoing Guide”. We also show that the chromatic index problem for regular k -cycle-free graphs of degree r , graphs of girth k , line graphs of bipartite graphs, line graphs of claw-free graphs, and for line graphs of C k -free graphs is NP-complete.
---
paper_title: Edge Dominating Sets in Graphs

paper_content:

We prove that the edge dominating set problem for graphs is $NP$-complete even when restricted to planar or bipartite graphs of maximum degree 3. We show as a corollary that the minimum maximal matching and the achromatic number problems are $NP$-complete. A new linear time algorithm for finding minimum independent edge dominating sets in trees is described, based on an observed relationship between edge dominating sets and independent sets in total graphs.
---
paper_title: Minimum edge dominating sets

paper_content:

Let $G = ( V,E )$ be a finite undirected graph with n vertices and m edges. A minimum edge dominating set of G is a set of edges D, of smallest cardinality $\gamma ' ( G )$, such that each edge of $E - D$ is adjacent to some edge of D. Let $S( G )$ be the subdivision graph of G and let $T( G )$ be the total graph of G. Let $\alpha ( G )$ be the stability number of G (cardinality of a largest stable set) and let $\alpha _2 ( G )$ be the 2-stability number of G (cardinality of a largest set of vertices in G, no two of which are joined by a path of length 2 or less). The following results are obtained. For any $G,\gamma' ( S ( G ) ) + \alpha _2 ( G ) = n$ and $2\gamma ' ( T ( G ) ) + \alpha ( T ( G ) ) = n + m$ or $n + m + 1$. Also, for any depth-first search tree S of $G,\gamma ' ( S )/2\leqq \gamma ' ( G )\leqq 2\gamma ' (S)$, and these bounds are tight.The edge domination problem is NP-complete for planar bipartite graphs, their subdivision, line, and total graphs, perfect claw-free graphs, and planar cub...
---
paper_title: Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance

paper_content:

This paper investigates cases where one graph parameter, upper fractional domination, is equal to three others: independence, upper domination and upper irredundance. We show that they are all equal for a large subclass, known as strongly perfect graphs, of the class of perfect graphs. They are also equal for odd cycles and upper bound graphs. However for simplicial graphs, upper irredundance might not equal the others, which are all equal. Also for many subclasses of perfect graphs other than the strongly perfect class, independence, upper domination and upper irredundance are not necessarily equal. We also show that if the graph join operation is used to combine two graphs which have some of the parameters equal, the resulting graph will have the same parameters equal.
---
paper_title: Generalizing NP-completeness proofs for bipartite graphs and chordal graphs

paper_content:

In this dissertation, we focus on developing general NP-complete constructions and applying them to a number of related graph problems. We will present original NP-completeness results, some of which are new, and others which are simpler proofs of existing NP-completeness results (see Table 2 and Table 3 in Chapter 6). All of the proofs of these results are no longer than two pages; most are less than one page long. The great majority of these results use reductions from the Exact Cover by 3 Sets problem and use a common graph construction. The full generality of this technique has not been fully developed and we suggest a number of "open" problems that may be shown NP-complete by applying similar techniques.
---
paper_title: Some covering concepts in graphs

paper_content:

Abstract A family of concepts involving maximum independent sets which have been under recent study are introduced. Interrelations among the concepts are pointed out and some recent relevant work is discussed.
---
paper_title: Well covered simplicial, chordal, and circular arc graphs

paper_content:

A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this paper, we characterize well covered simplicial, chordal and circular arc graphs. © 1996 John Wiley & Sons, Inc.
---
paper_title: Generalizing NP-completeness proofs for bipartite graphs and chordal graphs

paper_content:

In this dissertation, we focus on developing general NP-complete constructions and applying them to a number of related graph problems. We will present original NP-completeness results, some of which are new, and others which are simpler proofs of existing NP-completeness results (see Table 2 and Table 3 in Chapter 6). All of the proofs of these results are no longer than two pages; most are less than one page long. The great majority of these results use reductions from the Exact Cover by 3 Sets problem and use a common graph construction. The full generality of this technique has not been fully developed and we suggest a number of "open" problems that may be shown NP-complete by applying similar techniques.
---
paper_title: The Planar Hamiltonian Circuit Problem is NP-Complete

paper_content:

We consider the problem of determining whether a planar, cubic, triply-connected graph G has a Hamiltonian circuit. We show that this problem is NP-complete. Hence the Hamiltonian circuit problem for this class of graphs, or any larger class containing all such graphs, is probably computationally intractable.
---
paper_title: A polynomial characterization of some graph partitioning problems

paper_content:

Abstract The Uniform Partition (UP) and the Simple Max Partition (SMP) problems are NP-complete graph partitioning problems, and polynomial-time algorithms are known for few classes of graphs only. In the present paper, the class of line-graphs is considered and a polynomial algorithm is proposed to solve both problems in this class. When the instance space is extended to digraphs, a characterization is possible which leads to similar results.
---
paper_title: On the complexity of the Maximum Cut problem

paper_content:

The complexity of the SIMPLE MAX CUT problem is investigated for several special classes of graphs. It is shown that this problem is NP-complete when restricted to one of the following classes: chordal graphs, undirected path graphs, split graphs, tripartite graphs, and graphs that are the complement of a bipartite graph. The problem can be solved in polynomial time, when restricted to graphs with bounded treewidth, or cographs. We also give large classes of graphs that can be seen as generalizations of classes of graphs with bounded treewidth and of the class of cographs, and allow polynomial time algorithms for the SIMPLE MAX CUT problem.
---

Title: A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs

Section 1: Introduction
Description 1: Introduce the motivation and overview of the study, defining the special classes of graphs being investigated and summarizing their algorithmic properties.

Section 2: Classes of Graphs
Description 2: Define the various graph classes under study and describe their relationships. This includes simplicial graphs, upper bound graphs, middle graphs, and other related subclasses.

Section 3: Testing for Membership
Description 3: Review recognition algorithms for determining whether a given graph belongs to a specific class.

Section 4: Graph Properties
Description 4: Discuss the complexity of determining various graph properties, such as clique covers, independent sets, vertex covers, maximum clique, chromatic number, and chromatic index for the different graph classes.

Section 5: Dominating Set
Description 5: Analyze the complexity of finding minimum dominating sets and other related algorithmic problems in different classes of graphs.

Section 6: Edge Dominating Set
Description 6: Explore the algorithmic challenges and solutions related to finding edge dominating sets in various graph classes.

Section 7: Maximum Minimal Dominating Set
Description 7: Discuss the complexity and algorithms for determining the maximum minimal dominating set and related parameters.

Section 8: Irredundant Set
Description 8: Define the concept of irredundant sets and analyze their computational complexity within the studied graph classes.

Section 9: Minimum Dominating Independent Set and Minimum Maximal Irredundant Set
Description 9: Explore the properties and complexities of minimum dominating independent sets and minimum maximal irredundant sets in different graph classes.

Section 10: Hamiltonian Cycle/Path
Description 10: Investigate the problem of finding Hamiltonian cycles and paths, detailing the algorithmic complexity for each graph class.

Section 11: Induced Path
Description 11: Describe the complexity of finding induced paths in the studied graph classes.

Section 12: Graph Isomorphism
Description 12: Discuss the graph isomorphism problem and its complexity across different graph classes.

Section 13: Subgraph Isomorphism
Description 13: Examine the subgraph isomorphism problem and prove its NP-completeness in various graph classes.

Section 14: Steiner Tree
Description 14: Analyze the complexity of the Steiner Tree problem for the relevant graph classes, discussing reductions and NP-completeness proofs.

Section 15: Simple Maximum Cut
Description 15: Discuss the complexity of the simple maximum cut problem for the studied graph classes and point out open problems where applicable.