On the structure of graphs with few \(P_4\)s. (English) Zbl 0908.05065
This paper deals with the \(P_4\) structure of graphs (\(P_4\) denotes a path of length 3). A \((q,t)\) graph is one in which no set of \(q\) or fewer vertices induces more than \(t\) distinct \(P_4\)’s. The main result of this paper is that \((q,q-4)\) graphs form a class of graphs for which the isomorphism problem can be solved in polynomial time. The authors show that \((q,q-4)\) graphs can be encoded as rooted trees whose internal nodes represent certain graph operations and whose leaves correspond to certain basic graphs. As a result of this tree encoding isomorphism tests between \((q,q-4)\) graphs can be done in polynomial time. Another interesting result proved is that all \((q,q-4)\) graphs with \(4\leq q\leq 8\) are brittle. A graph \(G\) is brittle if each induced subgraph \(H\) of \(G\) contains a vertex which is either not the endpoint or not the midpoint of any \(P_4\) in \(H\). The graphs in this class are distinct from all previously known brittle graphs.
Reviewer: R.Molina (Alma)
MSC:
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0286.68029 |
| [2] | Babel, L.; Ponomarenko, I. N.; Tinhofer, G., The isomorphism problem for directed path graphs and for rooted directed path graphs, J. Algorithms, 21, 542-564 (1996) · Zbl 0864.68070 |
| [3] | L. Babel, Tree-like \(P_4\); L. Babel, Tree-like \(P_4\) |
| [4] | Booth, K. S.; Colbourn, C. J., Problems polynomially equivalent to graph isomorphism, (Report No. CS-77-04 (1979), Computer Science Department, University of Waterloo) |
| [5] | Booth, K. S.; Lueker, G. S., A linear time algorithm for deciding interval graph isomorphism, J. ACM, 26, 183-195 (1979) · Zbl 0402.68050 |
| [6] | Chvatal, V., Perfectly ordered graphs, (Berge, C.; Chvatal, V., Topics on Perfect Graphs (1984), North-Holland: North-Holland Amsterdam), 63-65 · Zbl 0559.05055 |
| [7] | Corneil, D. G.; Lerchs, H.; Burlingham, L. S., Complement reducible graphs, Discrete Appl. Math., 3, 163-174 (1981) · Zbl 0463.05057 |
| [8] | Corneil, D. G.; Perl, Y.; Stewart, L. K., A linear recognition algorithm for cographs, SIAM J. Comput., 14, 926-934 (1985) · Zbl 0575.68065 |
| [9] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 |
| [10] | Jamison, B.; Olariu, S., p-Components and the homogeneous decomposition of graphs, SIAM J. Discrete Math., 8, 448-463 (1995) · Zbl 0830.05056 |
| [11] | Jamison, B.; Olariu, S., A unique tree representation for \(P_4\)-sparse graphs, Discrete Appl. Math., 35, 115-129 (1992) · Zbl 0763.05092 |
| [12] | Jamison, B.; Olariu, S., Recognizing \(P_4\)-sparse graphs in linear time, SIAM J. Comput., 21, 381-406 (1992) · Zbl 0763.05093 |
| [13] | Jamison, B.; Olariu, S., \(P_4\)-reducible graphs, a class of uniquely tree representable graphs, Stud. Appl. Math., 81, 79-87 (1989) · Zbl 0699.05054 |
| [14] | Jamison, B.; Olariu, S., On a unique tree representation for \(P_4\)-extendible graphs, Discrete Appl. Math., 34, 151-164 (1991) · Zbl 0754.05051 |
| [15] | Jamison, B.; Olariu, S., A new class of brittle graphs, Stud. in Appl. Math., 81, 89-92 (1989) · Zbl 0701.05054 |
| [16] | Klawe, M. M.; Corneil, M. M.; Proskurowski, A., Isomorphism testing in hook-up graphs, SIAM J. Algebraic Discrete Methods, 3, 260-274 (1982) · Zbl 0503.05023 |
| [17] | Lawler, E. L., Graphical algorithms and their complexity, Math. Center Tracts, 81, 3-32 (1976) · Zbl 0358.68059 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
