scientific article; zbMATH DE number 4008429
From MaRDI portal
Publication:3758862
[For the entire collection see Zbl 0619.00006.] Given a connected cubic graph of order n, Payan, Tchuente and Yuong have shown that G contains a spanning tree with at least n/4 vertices of degree 3. They conjecture that n/4 can be replaced by n/3 if G contains no \(K_ 4-e\). We prove that if G has no triangles, then it has a spanning tree with \(\lfloor n/3\rfloor\) vertices of degree 3.
Recommendations
Cited in
(11)- 3-trees with few vertices of degree 3 in circuit graphs
- Spanning cubic graph designs
- The numbers of spanning trees of the cubic cycle \(C_ n^ 3\) and the quadruple cycle \(C_ n^ 4\)
- Number of vertices of degree three in spanning 3-trees in square graphs
- Cubic graphs with minimum number of spanning trees.
- Spanning trees in subcubic graphs.
- scientific article; zbMATH DE number 140143 (Why is no real title available?)
- Toughness, minimum degree, and spanning cubic subgraphs
- scientific article; zbMATH DE number 861398 (Why is no real title available?)
- A planar 3-connected, 3-regular graph without spanning Y-trees
- Arbres avec un nombre maximum de sommets pendants
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3758862)