Recognition and isomorphism of tree-like P₄-connected graphs

DOI10.1016/S0166-218X(99)00140-7MaRDI QIDQ1962050zbMATH OpenFDO

Authors Luitpold Babel

Publication date 26 April 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(99)00140-7

zbMATH Keywords

\(p\)-connected graphs\(p\)-trees\(P_4\)-structureisomorphismrecognition

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Graph theory (including graph drawing) in computer science (68R10)

Review text

The chordless path on four vertices is denoted by \(P_4\). A graph is \(P_4\)-connected if, for each partition of its vertices into two disjoint parts, there exists a \(P_4\) containing vertices from both parts. A \(p\)-tree is a \(P_4\)-connected graph in which each induced subgraph contains a vertex that belongs to at most one \(P_4\). Although a (\(P_4\)-connected) tree is, in general, not a \(p\)-tree, there are numerous tree-like characterizations of \(p\)-trees; see \textit{L. Babel} [Tree-like \(P_4\)-connected graphs, Discrete Math. 191, No. 1-3, 13-23 (1998)]. The author gives a new characterization of \(p\)-trees (Theorem 5.1) which allows him to recognize \(p\)-trees and to test isomorphism of \(p\)-trees in linear time.

Recommendations

• Tree-like P₄-connected graphs
• scientific article; zbMATH DE number 1051283
• scientific article; zbMATH DE number 4068899
• On the \(p\)-connectedness of graphs---a survey
• On a unique tree representation for \(P_ 4\)-extendible graphs

Cites work

• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A Linear Recognition Algorithm for Cographs
• A tree representation for \(P_ 4\)-sparse graphs
• Complement reducible graphs
• Graph theory with applications
• Hamiltonicity in graphs with few \(P_ 4\)'s
• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 4206028 (Why is no real title available?)
• scientific article; zbMATH DE number 1107719 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• On a unique tree representation for \(P_ 4\)-extendible graphs
• On the structure of graphs with few P₄s
• P-Components and the Homogeneous Decomposition of Graphs
• Recognizing P₄ -Sparse Graphs in Linear Time
• Tree-like P₄-connected graphs
• Triangulating graphs with few \(P_4\)'s
• Weakly triangulated graphs

Cited in

(13)

• On a unique tree representation for \(P_ 4\)-extendible graphs
• On the \(p\)-connectedness of graphs---a survey
• Tree- and forest-perfect graphs
• Recognizing the \(P_ 4\)-structures of a tree
• Tree-like P₄-connected graphs
• A time-based solution for the graph isomorphism problem
• scientific article; zbMATH DE number 4068899 (Why is no real title available?)
• scientific article; zbMATH DE number 1953107 (Why is no real title available?)
• scientific article; zbMATH DE number 2081001 (Why is no real title available?)
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Efficiently recognizing the P₄-structure of trees and of bipartite graphs without short cycles
• A new characterization of P₄-connected graphs

This page was built for publication: Recognition and isomorphism of tree-like \(P_4\)-connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962050)