An official website of the United States government
Abstract A spanning tree of a graph with no vertex of degree 2 is called a homeomorphically irreducible spanning tree (HIST) of the graph. In 1990, Albertson, Berman, Hutchinson, and Thomassen conjectured that every twin‐free graph with diameter 2 contains a HIST. Recently, Ando disproved this conjecture and characterized twin‐free graphs with diameter 2 that do contain a HIST. In this paper, we give a complete characterization of all graphs of diameter 2 that contain a HIST. This characterization gives alternative proofs for several known results.
more »
« less
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
-
Let $D=(V,A)$ be a digraph. A vertex set $$K\subseteq V$$ is a quasi-kernel of $$D$$ if $$K$$ is an independent set in $$D$$ and for every vertex $$v\in V\setminus K$$, $$v$$ is at most distance 2 from $$K$$. In 1974, Chvátal and Lovász proved that every digraph has a quasi-kernel. P. L. Erdős and L. A. Székely in 1976 conjectured that if every vertex of $$D$$ has a positive indegree, then $$D$$ has a quasi-kernel of size at most $|V|/2$. This conjecture is only confirmed for narrow classes of digraphs, such as semicomplete multipartite, quasi-transitive, or locally semicomplete digraphs. In this note, we state a similar conjecture for all digraphs, show that the two conjectures are equivalent, and prove that both conjectures hold for a class of digraphs containing all orientations of 4-colorable graphs (in particular, of all planar graphs).more » « less
