共查询到20条相似文献,搜索用时 0 毫秒
1.
We begin the study of sets of near 1-factors of graphs G of odd order whose union contains all the edges of G and determine, for a few classes of graphs, the minimum number of near 1-factors in such sets. 相似文献
2.
The triangle-spectrum for 2-factorizations of the complete graph Kv is the set of all numbers δ such that there exists a 2-factorization of Kv in which the total number of triangles equals δ. By applying mainly design-theoretic methods, we determine the triangle spectrum for all v ≡ 1 or 3 (mod 6), v ≥ 43, as well as for v = 7, 9, 13, 15, 21, and 27. For orders v = 19, 25, 31, 33, 37, 39, we leave only a total of 11 values undecided. To determine the triangle-spectrum for v ≡ 5 (mod 6) remains an open problem. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 83–94, 1997 相似文献
3.
Let be a 1‐factorization of the complete uniform hypergraph with and . We show that there exists a 1‐factor of whose edges belong to n different 1‐factors in . Such a 1‐factor is called a “rainbow” 1‐factor or an “orthogonal” 1‐factor. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 487–490, 2007 相似文献
4.
图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为x′_(vd)(G).用K_(2n)-E(C_4)表示2n阶完全图删去其中一条4阶路的边后得到的图,文中得到了K_(2n)-E(_4)的点可区别边色数. 相似文献
5.
A well known conjecture in graph theory states that every regular graph of even order 2n and degree λ(2n), where λ≥1/2, is 1-factorizable. Chetwynd and Hilton [A.G. Chetwynd, A.J.W. Hilton, 1-factorizing regular graphs of high degree — An improved bound, Discrete Math. 75 (1989) 103-112] and, independently, Niessen and Volkmann [T. Niessen, L. Volkmann, Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree, J. Graph Theory (2) 14 (1990) 225-246] proved the above conjecture under the assumption that . Since these results were published no significant or even partial improvement has been made in terms of lowering the bound on λ. We shall obtain here a partial improvement on λ. Specifically, using the original Chetwynd-Hilton approach and Tutte’s 1-Factor Theorem, we show that the above bound can be improved to , apart (possibly) from two families of exceptional cases. We then show, under the stronger assumption that λ≥λ∗≈0.785, that one of the two families of exceptional cases cannot occur. 相似文献
6.
Marco Buratti 《Journal of Combinatorial Theory, Series A》2005,111(2):245-256
We introduce the concept of a 2-starter in a group G of odd order. We prove that any 2-factorization of the complete graph admitting G as a sharply vertex transitive automorphism group is equivalent to a suitable 2-starter in G. Some classes of 2-starters are studied, with special attention given to those leading to solutions of some Oberwolfach or Hamilton-Waterloo problems. 相似文献
7.
A Note on Adjacent Strong Edge Coloring of K(n,m) 总被引:11,自引:0,他引:11
Jing-wen Li Zhong-fu Zhang Xiang-en Chen Yi-rong Sun 《应用数学学报(英文版)》2006,22(2):273-276
In this paper, we prove that the adjacent strong edge chromatic number of a graph K(n,m) is n + 1, with n ≥ 2, m ≥ 1. 相似文献
8.
KI,k-FACTORIZATION OF BIPARTITE GRAPHS 总被引:1,自引:0,他引:1
DUBELIANG 《高校应用数学学报(英文版)》1997,12(4):493-498
in this paper a necesssary condition for a bipartite graph λK,to be K1-factorizable and a sufficient condition for kk to have a k -factonrization whenever k is a prime number are given. 相似文献
9.
设f是图G的一个正常全染色.对任意x∈V(G),令C(x)表示与点x相关联或相邻的元素的颜色以及点x的颜色所构成的集合.若对任意u,v∈V(G),u≠v,有C(u)≠C(v),则称.f是图G的一个点强可区别全染色,对一个图G进行点强可区别全染色所需的最少的颜色的数目称为G的点强可区别全色数,记为X_(vst)(G).讨论了完全二部图K_(1,n),K_(2,n)和L_(3,n)的点强可区别全色数,利用组合分析法,得到了当n≥3时,X_(vst)(K_(1,n)=n+1,当n≥4时,X_(vst)(K_(2,n)=n+2,当n≥5时,X_(vst)(K_(3,n))=n+2. 相似文献
10.
Stanislav Jendrol' Jozef Miškuf Roman Soták Erika Škrabul'áková 《Journal of Graph Theory》2009,62(1):84-99
A face of an edge‐colored plane graph is called rainbow if the number of colors used on its edges is equal to its size. The maximum number of colors used in an edge coloring of a connected plane graph Gwith no rainbow face is called the edge‐rainbowness of G. In this paper we prove that the edge‐rainbowness of Gequals the maximum number of edges of a connected bridge face factor H of G, where a bridge face factor H of a plane graph Gis a spanning subgraph H of Gin which every face is incident with a bridge and the interior of any one face f∈F(G) is a subset of the interior of some face f′∈F(H). We also show upper and lower bounds on the edge‐rainbowness of graphs based on edge connectivity, girth of the dual graphs, and other basic graph invariants. Moreover, we present infinite classes of graphs where these equalities are attained. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 84–99, 2009 相似文献
11.
A graph is 1-toroidal, if it can be embedded in the torus so that each edge is crossed by at most one other edge. In this paper, it is proved that every 1-toroidal graph with maximum degree Δ≥ 10 is of class one in terms of edge coloring. Meanwhile, we show that there exist class two 1-toroidal graphs with maximum degree Δ for each Δ≤ 8. 相似文献
12.
Mirko Horňák Stanislav Jendrol′ Ingo Schiermeyer Roman Soták 《Journal of Graph Theory》2015,78(4):248-257
In the article, the existence of rainbow cycles in edge colored plane triangulations is studied. It is shown that the minimum number of colors that force the existence of a rainbow C3 in any n‐vertex plane triangulation is equal to . For a lower bound and for an upper bound of the number is determined. 相似文献
13.
We show that the edges of the complete multigraph 2K
mk+ 1 can be partitioned intomk + 1 factors, each the union ofmk-cycles, for all evenk, k 4.Both authors are grateful to the Mathematics Department at Queen's University for the hospitality extended to them while visiting.The author acknowledges the financial support of the Natural Sciences and Engineering Research Council of Canada under Grant No. A7829. 相似文献
14.
We show that there exists a family of r-regular graphs of arbitrarily large excessive index for each integer r greater than 3. Furthermore, we answer a question in Bonisoli and Cariolaro (2007) [1] showing that all the positive integers can be attained as excessive classes of regular graphs. 相似文献
15.
Abstract A k-edge-coloring f of a connected graph G is a (A1, A2, , A)-defected k-edge-coloring if there is a smallest integer/ with 1 _ /3 _〈 k - i such that the multiplicity of each color j E {1,2,... ,/3} appearing at a vertex is equal to Aj _〉 2, and each color of {/3 -}- 1,/3 - 2, - , k} appears at some vertices at most one time. The (A1, A2,, A/)-defected chromatic index of G, denoted as X (A1, A2,, A/; G), is the smallest number such that every (A1,A2,-.., A/)-defected t-edge-coloring of G holds t _〉 X(A1, A2 A;; G). We obtain A(G) X(A1, )2, , A/; G) + -- (Ai - 1) _〈 /k(G) 1, and introduce two new chromatic indices of G i=1 as: the vertex pan-biuniform chromatic index X pb (G), and the neighbour vertex pan-biuniform chromatic index Xnpb(G), and furthermore find the structure of a tree T having X pb (T) =1. 相似文献
16.
A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v, where uv ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by x′
Aa
(G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring
of some graphs and put forward some conjectures. 相似文献
17.
为了找到Km,n图的广义Mycielski图的全色数与边色数,用分析的方法,考虑不同情况,给出了它的全染色法与边染色法,得到了它的全色数与边色数. 相似文献
18.
Let G(V, E) be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if (1) C(u)≠C(v) for uv ∈ E(G), where C(u) = {f(uv)|uv ∈ E}, and (2) for any i, j = 1, 2,… k, we have ||Ei| |Ej|| ≤ 1, where Ei = {e|e ∈ E(G) and f(e) = i}. χáve (G) = min{k| there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χáve (G) of some special graphs and present a conjecture. 相似文献
19.
20.
In this note, we present some results concerning the chromatic index, the total chromatic index, the adjacent vertex distinguishing chromatic index and the adjacent vertex distinguishing total chromatic index for double graphs. In particular, we study the double graphs of class 1 and of type 1. 相似文献