无三角形3-正则图的几个参数的界

Bounds on Some Parameters in Triangle-free Cubic Graphs

图G的一条边称为割边是指删去该边后,使得余下的图的连通分支数增加。图G中的一个两两不相邻的边子集称为图G的一个匹配。图G的一个最大匹配的边数称为图G的匹配数。图G中的一个与G的每个团都有交的顶点子集称为G的一个团横贯集,图G中元素个数最少的团横贯集的顶点数称为G的团横贯数。本文针对n阶连通无三角形的3-正则图G=(V(G),E(G)),首先给出了其割边数的一个上界(n-10)/4;其次对它的匹配数得到了一个下界(11n-2)/24;再次对它的线图的团横贯数呈现了一个上界(13 E(G)+3)/36。同时刻画了达到这些界的极值图。

A cut-edge in a graph G is an edge whose removal increases the number of connected components of the graph. A matc- hing of G is a set of pairwise independent edges of G. The matching number is the number of edges in a maximum matching of G. A vertices set is called a clique-transversal set of G if it meets all cliques of G. The clique-transversal number is the minimum cardinali- ty of a clique-transversal set of G. In this paper, for a connected triangle-free cubic graph G= （W（G）,E（G）） of order n, firstly, we give an upper bound （n--10）/4 on the number of cut-edges. Secondly, we get a lower bound （ 11n-2）/24 on the matching number. Thirdly, we present an upper bound （13 ｜ E（G） ｜ ＋3）/36 on the clique-transversal number for the line graph of G. Meanwhile, we characterize the extremal graph sachieving these bounds.