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)
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)
