Recognizing k-path graphs

DOI10.1016/S0166-218X(99)00132-8zbMATH Open0941.05042MaRDI QIDQ1962042FDOQ1962042

Authors: Erich Prisner 

Publication date: 3 August 2000

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

Recommendations

• scientific article; zbMATH DE number 1107738
• Polar cographs
• Path graphs
• 4-path graphs: a generalization of line graphs
• Two new characterizations of path graphs

zbMATH Keywords

characterizationrecognition algorithmgraph recognition\(k\)-path graphpolarized graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Cites Work

• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Title not available (Why is that?)
• On the characterization of path graphs
• Path graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Bicliques in graphs. I: Bounds on their number
• Title not available (Why is that?)
• P3-isomorphisms for graphs
• Isomorphisms ofP3-graphs

Cited In (12)

• Histories in Path Graphs
• Recognizing Bellman–Ford-Orderable Graphs
• Title not available (Why is that?)
• On the determination problem for \(P_{4}\)-transformation of graphs
• Two new characterizations of path graphs
• Path-bicolorable graphs. (Extended abstract)
• Title not available (Why is that?)
• Histories in path graphs
• Recognizing clique graphs of directed and rooted path graphs
• On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths
• From path graphs to directed path graphs
• Path-bicolorable graphs

This page was built for publication: Recognizing \(k\)-path graphs

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