On even cycle decompositions of line graphs of cubic graphs
4
Citation
17
Reference
10
Related Paper
Citation Trend
Keywords:
Indifference graph
Cubic graph
Line (geometry)
Fast algorithms can be created for many graph problems when instances are confined to classes of graphs that are recursively constructed. This article first describes some basic conceptual notions regarding the design of such fast algorithms, and then the coverage proceeds through several recursive graph classes. Specific classes include trees, series-parallel graphs, k -terminal graphs, treewidth- k graphs, k -trees, partial k -trees, k -jackknife graphs, pathwidth- k graphs, bandwidth- k graphs, cutwidth- k graphs, branchwidth- k graphs, Halin graphs, cographs, cliquewidth- k graphs, k -NLC graphs, k -HB graphs, and rankwidth- k graphs. The definition of each class is provided. Typical algorithms are applied to solve problems on instances of most classes. Relationships between the classes are also discussed.
Indifference graph
Clique-sum
Treewidth
Partial k-tree
Cograph
Maximal independent set
Modular decomposition
Cite
Citations (28)
Treewidth
Clique-sum
Partial k-tree
Indifference graph
Maximal independent set
Tree-depth
Vertex cover
Cograph
Cite
Citations (57)
We consider the problem of determining the path-distance-width for AT-free graphs and graphs in related classes such as k-cocomparability graphs, proper interval graphs, cobipartite graphs, and cochain graphs. We first show that the problem is NP-hard even for cobipartite graphs, and thus for AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for AT-free graphs and graphs in the related graph classes mentioned above. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for cochain graphs, which form a subclass of the class of proper interval graphs.
Indifference graph
Maximal independent set
Modular decomposition
Cograph
Clique-sum
Metric Dimension
Split graph
Trapezoid graph
Induced path
Block graph
Graph product
Cite
Citations (1)
Interval and proper interval graphs are very well-known graph classes, for which there is a wide literature. As a consequence, some generalizations of interval graphs have been proposed, in which graphs in general are expressed in terms of $k$ interval graphs, by splitting the graph in some special way. As a recent example of such an approach, the classes of $k$-thin and proper $k$-thin graphs have been introduced generalizing interval and proper interval graphs, respectively. The complexity of the recognition of each of these classes is still open, even for fixed $k \geq 2$. In this work, we introduce a subclass of $k$-thin graphs (resp. proper $k$-thin graphs), called precedence $k$-thin graphs (resp. precedence proper $k$-thin graphs). Concerning partitioned precedence $k$-thin graphs, we present a polynomial time recognition algorithm based on $PQ$-trees. With respect to partitioned precedence proper $k$-thin graphs, we prove that the related recognition problem is \NP-complete for an arbitrary $k$ and polynomial-time solvable when $k$ is fixed. Moreover, we present a characterization for these classes based on threshold graphs.
Indifference graph
Maximal independent set
Interval graph
Cograph
Graph product
Trapezoid graph
Clique-sum
Modular decomposition
Cite
Citations (0)
We describe and implement two local reduction rules that can be used to recognize Halin graphs in linear time, avoiding the complicated planarity testing step of previous linear time Halin graph recognition algorithms. The same two rules can be used as the basis for linear-time algorithms for other algorithmic problems on Halin graphs, including decomposing these graphs into a tree and a cycle, finding a Hamiltonian cycle, or constructing a planar embedding. These reduction rules can also be used to recognize a broader class of polyhedral graphs. These graphs, which we call the D3-reducible graphs, are the dual graphs of the polyhedra formed by gluing pyramids together on their triangular faces; their treewidth is bounded, and they necessarily have Lombardi drawings.
Treewidth
Clique-sum
Indifference graph
Planarity testing
Book embedding
Partial k-tree
Cite
Citations (8)
The Laplace polynomials of MS graphs and MCS graphs which were based on cycles or paths were gotten.Then the formulas were derived for the Kirchhoff index of the complement of cycle Cn or path Pn and some other graphs such as the MSCR graphs,MCCR graphs,MSPR graphs and MCPR graphs.
Indifference graph
Complement
Clique-sum
Modular decomposition
Metric Dimension
Maximal independent set
Cite
Citations (1)
Indifference graph
Cograph
Clique-sum
Split graph
Maximal independent set
Modular decomposition
Disjoint sets
Interval graph
Treewidth
Partial k-tree
Cite
Citations (53)
This chapter describes the history of graphs and introduces the main definitions of graphs. It discusses some particular classes of graphs that we can meet in philosophy and provides some examples of them. The chapter presents a list of well-known graphs that we can put together according to their name. A graph generally has different kinds of drawings, but all of these are isomorphic. So, a graph is in fact a class of graphs generally defined up to an isomorphism. Even when graphs are non-separable, they always admit subgraphs. Informally speaking, the reconstruction conjecture says that graphs are determined uniquely by their subgraphs. The conjecture has been verified for a number of infinite classes of graphs: regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs without end vertices, maximal planar graphs, maximal outerplanar graphs, outerplanar graphs and critical blocks.
Indifference graph
Clique-sum
Maximal independent set
Metric Dimension
Cograph
Trapezoid graph
Modular decomposition
Partial k-tree
Cite
Citations (0)
In this paper it is determined when the line graphs and the middle graphs of some classes of graphs are divisor graphs. Complete characterizations for cycles, trees, complete graphs and complete multipartite graphs whose line graphs (middle graphs) are divisor graphs are obtained. It is also shown that the line graphs and the middle graphs of the cycle permutation graphs are never divisor graphs.
Indifference graph
Trapezoid graph
Cograph
Clique-sum
Modular decomposition
Maximal independent set
Graph product
Split graph
Metric Dimension
Cite
Citations (1)
Indifference graph
Clique-sum
Graph product
Cograph
Maximal independent set
Split graph
Brooks' theorem
Trapezoid graph
Cite
Citations (3)