Minimal regular 2-graphs and applications

DOI10.1007/S11425-004-5192-YMaRDI QIDQ854642zbMATH OpenOpenAlexFDO

Authors Hongbing Fan, Guizhen Liu, Jiping Liu

Publication date 6 December 2006

Published in Science in China. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11425-004-5192-y

zbMATH Keywords

2-graphgraphregular factor

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

A 2-graph is a hypergraph with edge sizes at most two. It is minimal if it does not contain a proper regular factor. Let \(f_2(n)\) be the maximum value of degrees over all minimal 2-graphs of \(n\) vertices. In this paper the authors prove that \(f_2(n) = \frac{n+3-i}{3}\), for \(n \geq 7\) and \(i = n \pmod 6\). This can be used in graph theory to characterize unfactorable regular graphs and to provide the best possible factor existence theorem on degree conditions.

Recommendations

• Minimum 2-dominating sets in regular graphs
• On \((2,r)\)-regular graphs
• Some minimal \((r, 2, k)\)-regular graphs containing a given graph
• Minimal 2-matching-covered graphs
• Minimal capillary graphs over regular \(2n\)-gons
• Graphs whose minimal rank is two
• Two-dimensional disjoint minimal graphs
• scientific article; zbMATH DE number 3950569
• On the minor-minimal 2-connected graphs having a fixed minor
• Edge-minimal graphs of exponent 2

Cites work

• An efficient incremental algorithm for solving systems of linear diophantine equations
• Graph theory with applications
• scientific article; zbMATH DE number 3900787 (Why is no real title available?)
• Isomorphic factorizations X: Unsolved problems
• Ordering by Divisibility in Abstract Algebras
• The Factorization of Linear Graphs

Cited in

(3)

• Minimum 2-dominating sets in regular graphs
• The existence of even regular factors of regular graphs on the number of cut edges
• The trace-minimal graph with \(2v\) vertices and regularity \(v+1\)

This page was built for publication: Minimal regular 2-graphs and applications

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