For any tree T with nodes all of degree 1 or 3, define an expansion of T as a cubic graph in which each node of T is replaced by a segment of n vertices, where n is an integer greater than 2, which are joined so that: (1) a leaf of T is replaced by a cycle of length n, the edges joining vertices in an arithmetic sequence; (2) a node of degree three is replaced by n disjoint vertices; (3) an edge of T is replaced by n edges joining corresponding vertices in the appropriate segments. Frucht, Graver and Watkins have shown that there are only six expansions of the tree consisting of a single edge, that is, the generalized Petersen graphs, that are symmetric. This paper shows that there are only six other expansions of trees that are symmetric. Four are Y-graphs, expansions of \(K_{1,3}\), and two are H-graphs, expansions of the tree with two nodes of degree 3 and four nodes of degree 1. All these symmetric graphs were listed in Foster's Census in 1966.
- Hamiltonian paths in vertex-symmetric graphs of order 4p
- Hamiltonian paths in vertex-symmetric graphs of order 5p
- scientific article; zbMATH DE number 3943850 (Why is no real title available?)
- scientific article; zbMATH DE number 193034 (Why is no real title available?)
- scientific article; zbMATH DE number 3349883 (Why is no real title available?)
- scientific article; zbMATH DE number 3046496 (Why is no real title available?)
- Lifting Hamilton cycles of quotient graphs
- On Hamiltonian Cycles in Metacirculant Graphs
- Three Remarkable Graphs
- Isomorphism checking of \(I\)-graphs
- Complexity of the circulant foliation over a graph
- Modelling and solving the perfect edge domination problem
- Complexity of discrete Seifert foliations over a graph
- Counting rooted spanning forests for circulant foliation over a graph
- New Constructions of Groups Without Semiregular Subgroups
- Hamiltonian cycles in covering graphs of trees
- Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians
- On the structure of Laplacian characteristic polynomial for circulant foliation
- On Jacobian group and complexity of the -graph
- Hamiltonian cycles in cubic Cayley graphs: The \(\langle 2,4k,3\rangle \) case
- Vertex-transitive expansions of (1, 3)-trees
This page was built for publication: Symmetric Y-graphs and H-graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1264159)
