Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

DOI10.1016/J.DISC.2006.06.026MaRDI QIDQ864162zbMATH OpenOpenAlexFDO

Authors Ching-Chi Lin, Gen-Huey Chen, Gerard Jennhwa Chang

Publication date 13 February 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.06.026

zbMATH Keywords

algorithmcircular-arc graphdirected path graphinterval graphlocally connected spanning treeproper circular-arc graphstrongly chordal graph

Mathematics Subject Classification ID

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

Review text

A spanning tree \(T\) of a graph \(G=(V,E)\) is locally connected if for all \(v \in V\) the subgraph of \(G\) induced by \(N_T(v)\) is connected. \textit{L. Cai} [Discrete Appl. Math. 131, 63--75 (2003; Zbl 1022.05079)] showed that it is NP-complete to decide whether a graph has a locally connected spanning tree. Restricted to strongly chordal graphs and circular-arc graphs this problem becomes solvable in linear time, if a simple elimination ordering or arc-intersection model is provided with the input.

Recommendations

• Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs
• A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
• The complexity of the locally connected spanning tree problem
• scientific article; zbMATH DE number 1979496
• A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs

Cites work

• Characterizations of strongly chordal graphs
• Characterizations of totally balanced matrices
• Doubly lexical ordering of dense 0--1 matrices
• Doubly Lexical Orderings of Matrices
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Linear-time recognition of circular-arc graphs
• Networks immune to isolated failures
• Networks immune to isolated line failures
• On spanning 2-trees in a graph
• Steiner trees, partial 2–trees, and minimum IFI networks
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• The complexity of the locally connected spanning tree problem
• Three Partition Refinement Algorithms
• Totally-Balanced and Greedy Matrices

Cited in

(6)

• Local strongly arc-connectivity in regular bipartite digraphs
• The complexity of the locally connected spanning tree problem
• Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs
• A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs
• A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
• Spanning trees: A survey

This page was built for publication: Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

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