On primal graphs with maximum degree 2

MaRDI QIDQ2875908zbMATH OpenFDO

Authors D. J. Lipman, R. B. Richter

Publication date 12 August 2014

Published in JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing (Search for Journal in Brave)

zbMATH Keywords

graph decompositionsprimal graphs

Mathematics Subject Classification ID

Graph designs and isomorphic decomposition (05C51) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Primal graphs are graphs such that every graph is either primal or has an edge-decomposition into non-isomorphic primal graphs. For example, the graphs \(2^iK_2\), \(2^iK_{1,2}\), \(C_5+K_2\) and \(7C_5+K_2\) are primal. The authors define a new parameter, which determines how far a graph is from having an edge-decomposition into graphs of the form \(2^iK_2\) and those of the form \(2^iK_{1,2}\), and show that graphs with a small value of this parameter can be edge-decomposed into non-isomorphic graphs of the form \(2^iK_2\), \(2^iK_{1,2}\), \(C_5+K_2\) and \(7C_5+K_2\).

Recommendations

• scientific article; zbMATH DE number 4181369
• scientific article; zbMATH DE number 861331
• scientific article; zbMATH DE number 4142075
• Primal graphs with small degrees
• scientific article; zbMATH DE number 19180

Cited in

(5)

• On edge-primitive graphs of order twice a prime power
• Maximal-\(\Gamma\)-prime Graphen
• scientific article; zbMATH DE number 4181369 (Why is no real title available?)
• The maximum number of vertices of primitive regular graphs of orders 2, 3, 4 with exponent 2
• Tiling paths with primal graphs

This page was built for publication: On primal graphs with maximum degree 2

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