In graph theory, a path generated in an undirected graph G is a path that is a generated subgraph of G. Thus, this is a sequence of vertices in G such that any two adjacent vertices in the sequence are connected by an edge in G , and any two non-adjacent vertices of the sequence are not connected by an edge of G. The generated path is sometimes called a snake, and the task of finding the longest generated path in hypercube graphs is known as the snake in box problem.
Also, a generated cycle is a cycle that is a generated subgraph of G. Generated cycles are also called cycles without chords or (if the cycle length is at least four) holes . The anti -hole is the hole in the complement of column G , that is, the anti-hole is the complement of the hole.
The length of the largest path generated in a graph is sometimes called the traversal number of the graph [1] . For sparse graphs, the existence of a limited number of traversals is equivalent to the existence of a limited depth of a tree [2] . The generated traversal number of a graph G is the smallest number of subsets of vertices into which the vertices of the graph can be decomposed so that each subset forms a generated path [3] , and this concept is closely related to the number of path coverage - the minimum number of disconnected paths that are generated by the subgraphs G covering all vertices of G [4] . The graph girth is the length of its shortest cycle, but this cycle must be a generated cycle, since any chord could form a shorter cycle. For the same reasons, the odd girth of a graph is the length of its shortest odd generated cycle.
Content
Example
The figure shows a cube, a graph with eight vertices, twelve edges and a path generated by a length of four. A direct analysis shows that there is no longer generated path in the cube, although there is an generated cycle of length six. The problem of finding the largest generated path or cycle in a hypercube, first posed by Kautz [5] , is known as the problem of a snake in a box and has been studied intensively due to its use in coding theory and design.
Description of graph families
Many important families of graphs can be described in terms of the generated paths or cycles of graphs in the family.
- Obviously, connected graphs that do not have generated paths of length two are complete graphs , and connected graphs without generated cycles are trees .
- A graph without triangles is a graph without generated cycles of length three.
- Cographs are precisely graphs without generated paths of length three.
- Chordal graphs are graphs without generated cycles of length four or more.
- are graphs that do not have cycles containing an even number of vertices.
- Trivially perfect graphs are graphs in which there are neither generated paths of length three nor generated cycles of length four.
- According to the strict theorem on perfect graphs, perfect graphs are graphs without odd holes and odd anti-holes.
- Remote-inherited graphs are graphs in which any generated path is the shortest, and in these graphs any two generated paths between two vertices have the same length.
- Block graphs are graphs in which there is at most one generated path between any two vertices, and connected block graphs are graphs in which there is exactly one generated path between any two vertices.
Algorithms and Complexity
The problem of determining whether a graph G has a generated path of length at least k is NP-complete. Garey and Johnson [6] expressed this result in an unpublished report to Michalis Yannakakis . However, this problem can be solved in polynomial time for certain families of graphs, such as graphs without asteroid triples [7] or graphs without long holes [8] .
It is also an NP-complete problem to determine if the vertices of the graph can be decomposed into two generated paths or two generated cycles [9] . As a result, determining the number of generated paths of a graph is an NP-hard problem.
The complexity of the approximation problems for the largest generated path or cycle can be related to the problem of finding the largest independent sets in graphs [10] .
Holes (and anti-holes in graphs without cycles of length 5 without chords) in a graph with n vertices and m edges can be found in time (n + m 2 ) [11] .
Atomic cycles
Atomic cycles are a generalization of cycles without chords. If a cycle is given, an n- chord is defined as a path of length n containing two points of the cycle, where n is less than the length of the shortest path in the cycle connecting these points. If a cycle does not have n- chords, it is called an atomic cycle, since it cannot be divided into smaller cycles [12] . In the worst case, atomic cycles in a graph can be listed in O ( m 2 ) time, where m is the number of edges in the graph.
Notes
- ↑ Buckley, Harary, 1988 .
- ↑ Nešetřil, Ossona de Mendez, 2012 , Proposition 6.4, p. 122.
- ↑ Chartrand et al., 1994 .
- ↑ Barioli, Fallat, Hogben, 2004 .
- ↑ Kautz, 1958 .
- ↑ Garey, Johnson, 1979 .
- ↑ Kratsch, Müller, Todinca, 2003 .
- ↑ Gavril, 2002 .
- ↑ Le, Le, Müller, 2003 .
- ↑ Berman, Schnitger, 1992 .
- ↑ Nikolopoulos, Palios, 2004 .
- ↑ Gashler, Martinez, 2012 .
Literature
- Francesco Barioli, Shaun Fallat, Leslie Hogben. Computation of minimal rank and path cover number for certain graphs // Linear Algebra Appl .. - 2004. - T. 392 . - S. 289-303 . - DOI : 10.1016 / j.laa.2004.06.06.019 .
- Piotr Berman, Georg Schnitger. On the complexity of approximating the independent set problem // Information and Computation. - 1992 .-- T. 96 . - S. 77-94 . - DOI : 10.1016 / 0890-5401 (92) 90056-L .
- Fred Buckley, Frank Harary. On longest induced paths in graphs // Chinese Quart. J. Math. - 1988 .-- T. 3 . - S. 61-65 .
- Gary Chartrand, Joseph McCanna, Naveed Sherwani, Moazzem Hossain, Jahangir Hashmi. The induced path number of bipartite graphs // Ars Combin .. - 1994 .-- T. 37 . - S. 191-208 .
- Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness .. - WH Freeman, 1979. - S. 196.
- Michael Gashler, Tony Martinez. Robust manifold learning with CycleCut // Connection Science. - 2012 .-- T. 24 , no. 1 . - S. 57-69 . - DOI : 10.1080 / 09540091.2012.664122 .
- Fănică Gavril. Algorithms for maximum weight induced paths // Information Processing Letters. - 2002. - T. 81 , no. 4 . - S. 203-208 . - DOI : 10.1016 / S0020-0190 (01) 00222-8 .
- Johan Håstad. Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. - 1996. - S. 627-636. - DOI : 10.1109 / SFCS.1996.548522 .
- WH Kautz. Unit-distance error-checking codes // IRE Trans. Elect. Comput .. - 1958.- T. 7 . - S. 177-180 .
- Dieter Kratsch, Haiko Müller, Ioan Todinca. Graph-theoretic concepts in computer science. - Berlin: Lecture Notes in Computer Science, Vol. 2880, Springer-Verlag, 2003. - S. 309-321. - DOI : 10.1007 / b93953 . Archived on November 25, 2006.
- Hoàng-Oanh Le, Van Bang Le, Haiko Müller. Splitting a graph into disjoint induced paths or cycles // Discrete Appl. Math .. - 2003.- T. 131 , no. 1 . - S. 199-212 . - DOI : 10.1016 / S0166-218X (02) 00425-0 .
- Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. - Heidelberg: Springer, 2012 .-- T. 28. - S. 115-144. - (Algorithms and Combinatorics). - ISBN 978-3-642-27874-7 . - DOI : 10.1007 / 978-3-642-27875-4 .
- Stavros D. Nikolopoulos, Leonidas Palios. Proc. 15th ACM-SIAM Symposium on Discrete Algorithms. - 2004 .-- S. 850-859.