A 2-graph is a hypergraph with edge sizes of at most two.A regular 2-graph is said to be minimal if it does not contain a proper regular factor.Let f2(n)be the maximum value of degrees over all minimal regular 2-graph...A 2-graph is a hypergraph with edge sizes of at most two.A regular 2-graph is said to be minimal if it does not contain a proper regular factor.Let f2(n)be the maximum value of degrees over all minimal regular 2-graphs of n vertices.In this paper,we provide a structure property of minimal regular 2-graphs,and consequently,prove that f2(n)=n+3-i/3,where 1≤i≤6,i≡n(mod 6)and n≥7,which solves a conjecture posed by Fan,Liu,Wu and Wong.As applications in graph theory,we are able to characterize unfactorable regular graphs and provide the best possible factor existence theorem on degree conditions.Moreover,fa(n)and the minimal 2-graphs can be used in the universal switch box designs,which originally motivated this study.展开更多
基金supported by the Natural Sciences and Engineering Research Council of Canadathe National Natural Science Foundation of China(Grant No.10471078)Specialied Research Fund for the Doctoral Program of Higher Education(Grant No.20040422004)of China.
文摘A 2-graph is a hypergraph with edge sizes of at most two.A regular 2-graph is said to be minimal if it does not contain a proper regular factor.Let f2(n)be the maximum value of degrees over all minimal regular 2-graphs of n vertices.In this paper,we provide a structure property of minimal regular 2-graphs,and consequently,prove that f2(n)=n+3-i/3,where 1≤i≤6,i≡n(mod 6)and n≥7,which solves a conjecture posed by Fan,Liu,Wu and Wong.As applications in graph theory,we are able to characterize unfactorable regular graphs and provide the best possible factor existence theorem on degree conditions.Moreover,fa(n)and the minimal 2-graphs can be used in the universal switch box designs,which originally motivated this study.
基金Supported by National Natural Science Foundation of China(No.11071002)Program for New Century Excellent Talents in University,Key Project of Chinese Ministry of Education(No.210091)+4 种基金Specialized Research Fund for the Doctoral Program of Higher Education(No.20103401110002)Science and Technological Fund of Anhui Province for Outstanding Youth(No.10040606Y33)National Science Foundation of the Department of Education of Anhui Province(Nos.KJ2011A195,KJ2010B136)Scientific Research Fund for Fostering Distinguished Young Scholars of Anhui University(No.KJJQ1001)Project for Academic Innovation Team of Anhui University(No.KJTD001B)
