共查询到20条相似文献,搜索用时 31 毫秒
1.
A graph G is close to regular or more precisely a (d, d + k)-graph, if the degree of each vertex of G is between d and d + k. Let d ≥ 2 be an integer, and let G be a connected bipartite (d, d+k)-graph with partite sets X and Y such that |X|- |Y|+1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d +7 when k = 1,·n ≥ 4d+ 5 when k = 2,·n ≥ 4d+3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible. 相似文献
2.
For any d?5 and k?3 we construct a family of Cayley graphs of degree d, diameter k, and order at least k((d?3)/3)k. By comparison with other available results in this area we show that our family gives the largest currently known Cayley graphs for a wide range of sufficiently large degrees and diameters. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 87–98, 2010 相似文献
3.
Let BCd,k be the largest possible number of vertices in a bipartite Cayley graph of degree d and diameter k. We show that BCd,k≥2(k−1)((d−4)/3)k−1 for any d≥6 and any even k≥4, and BCd,k≥(k−1)((d−2)/3)k−1 for d≥6 and k≥7 such that k≡3 (mod 4). 相似文献
4.
Xuding Zhu 《Journal of Graph Theory》2005,48(3):186-209
For 1 ≤ d ≤ k, let Kk/d be the graph with vertices 0, 1, …, k ? 1, in which i ~j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χc(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to Kk/d. The circular clique number ωc(G) of G is the maximum of those k/d for which Kk/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χc(H) = ωc(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, NG[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, NG[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P5 (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph Kk/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005 相似文献
5.
Guojun Li 《Journal of Graph Theory》2000,35(1):8-20
Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2(k + 1)‐connected graph G,d G (u,v) = 2 implies that max{d(u;G), d(v;G)} ≥ (n/2) + 2k, then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000 相似文献
6.
For a positive integer d, the usual d‐dimensional cube Qd is defined to be the graph (K2)d, the Cartesian product of d copies of K2. We define the generalized cube Q(Kk, d) to be the graph (Kk)d for positive integers d and k. We investigate the decomposition of the complete multipartite graph K into factors that are vertex‐disjoint unions of generalized cubes Q(Kk, di), where k is a power of a prime, n and j are positive integers with j ≤ n, and the di may be different in different factors. We also use these results to partially settle a problem of Kotzig on Qd‐factorizations of Kn. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 144–150, 2000 相似文献
7.
For k = 1 and k = 2, we prove that the obvious necessary numerical conditions for packing t pairwise edge‐disjoint k‐regular subgraphs of specified orders m1,m2,… ,mt in the complete graph of order n are also sufficient. To do so, we present an edge‐coloring technique which also yields new proofs of various known results on graph factorizations. For example, a new construction for Hamilton cycle decompositions of complete graphs is given. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 499–506, 2008 相似文献
8.
Tomoki Nakamigawa 《Journal of Graph Theory》2007,56(3):159-166
Let k be a fixed integer at least 3. It is proved that every graph of order (2k ? 1 ? 1/k)n + O(1) contains n vertex disjoint induced subgraphs of order k such that these subgraphs are equivalent to each other and they are equivalent to one of four graphs: a clique, an independent set, a star, or the complement of a star. In particular, by substituting 3 for k, it is proved that every graph of order 14n/3 + O(1) contains n vertex disjoint induced subgraphs of order 3 such that they are equivalent to each other. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 159–166, 2007 相似文献
9.
Let G=(V1,V2;E) be a bipartite graph with |V1|=|V2|=3k, where k>0. In this paper it is proved that if d(x)+d(y)≥4k−1 for every pair of nonadjacent vertices x∈V1, y∈V2, then G contains k−1 independent cycles of order 6 and a path of order 6 such that all of them are independent. Furthermore, if d(x)+d(y)≥4k for every pair of nonadjacent vertices x∈V1, y∈V2 and k>2, then G contains k−2 independent cycles of order 6 and a cycle of order 12 such that all of them are independent. 相似文献
10.
11.
Daniel W. Cranston Anja Pruchnewski Zsolt Tuza Margit Voigt 《Journal of Graph Theory》2012,71(1):18-30
The following question was raised by Bruce Richter. Let G be a planar, 3‐connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), 6} for all v∈V(G)? More generally, we ask for which pairs (r, k) the following question has an affirmative answer. Let r and k be the integers and let G be a K5‐minor‐free r‐connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), k} for all v∈V(G)? We investigate this question by considering the components of G[Sk], where Sk: = {v∈V(G)|d(v)8k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d(Sk) in G between the components of G[Sk]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18–30, 2012 相似文献
12.
For two vertices u and v of a graph G, the closed interval I[u, v] consists of u, v, and all vertices lying in some u–v geodesic of G, while for S V(G), the set I[S] is the union of all sets I[u, v] for u, v S. A set S of vertices of G for which I[S] = V(G) is a geodetic set for G, and the minimum cardinality of a geodetic set is the geodetic number g(G). A vertex v in G is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in G is its extreme order ex(G). A graph G is an extreme geodesic graph if g(G) = ex(G), that is, if every vertex lies on a u–v geodesic for some pair u, v of extreme vertices. It is shown that every pair a, b of integers with 0 a b is realizable as the extreme order and geodetic number, respectively, of some graph. For positive integers r, d, and k 2, it is shown that there exists an extreme geodesic graph G of radius r, diameter d, and geodetic number k. Also, for integers n, d, and k with 2 d > n, 2 k > n, and n – d – k + 1 0, there exists a connected extreme geodesic graph G of order n, diameter d, and geodetic number k. We show that every graph of order n with geodetic number n – 1 is an extreme geodesic graph. On the other hand, for every pair k, n of integers with 2 k n – 2, there exists a connected graph of order n with geodetic number k that is not an extreme geodesic graph. 相似文献
13.
Petra Johann 《Journal of Graph Theory》2000,35(4):227-243
In this paper we study the structure of graphs with a unique k‐factor. Our results imply a conjecture of Hendry on the maximal number m (n,k) of edges in a graph G of order n with a unique k‐factor: For we prove and construct all corresponding extremal graphs. For we prove . For n = 2kl, l ∈ ℕ, this bound is sharp, and we prove that the corresponding extremal graph is unique up to isomorphism. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 227–243, 2000 相似文献
14.
Ken‐ichi Kawarabayashi Haruhide Matsuda Yoshiaki Oda Katsuhiro Ota 《Journal of Graph Theory》2002,39(3):188-193
Let ? be a set of connected graphs. An ?‐factor of a graph is its spanning subgraph such that each component is isomorphic to one of the members in ?. Let Pk denote the path of order k. Akiyama and Kano have conjectured that every 3‐connected cubic graph of order divisible by 3 has a {P3}‐factor. Recently, Kaneko gave a necessary and sufficient condition for a graph to have a {P3, P4, P5}‐factor. As a corollary, he proved that every cubic graph has a {P3, P4, P5}‐factor. In this paper, we prove that every 2‐connected cubic graph of order at least six has a {Pk ∣ k ≥ , 6}‐factor, and hence has a {P3, P4}‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 188–193, 2002; DOI 10.1002/jgt.10022 相似文献
15.
The clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all . 相似文献
16.
Michael Ferrara Ronald Gould Michael Jacobson Florian Pfender Jeffrey Powell Thor Whalen 《Journal of Graph Theory》2012,71(1):69-77
For a fixed (multi)graph H, a graph G is H‐linked if any injection f: V(H)→V(G) can be extended to an H‐subdivision in G. The notion of an H ‐linked graph encompasses several familiar graph classes, including k‐linked, k‐ordered and k‐connected graphs. In this article, we give two sharp Ore‐type degree sum conditions that assure a graph G is H ‐linked for arbitrary H. These results extend and refine several previous results on H ‐linked, k‐linked, and k‐ordered graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:69–77, 2012 相似文献
17.
Multithreshold graphs are defined in terms of a finite sequence of real thresholds that break the real line into a set of regions, alternating between NO and YES. If real ranks can be assigned to the vertices of a graph in such a way that two vertices are adjacent iff the sum of their ranks lies in a YES region, then that graph is a multithreshold graph with respect to the given set of thresholds. If a graph can be represented with k or fewer thresholds, then it is k-threshold. The case of one threshold is the classical case introduced by Chvátal and Hammer. In this paper, we show for every graph G, there is a k such that G is k-threshold, and we exhibit graphs for which the required number of thresholds is linear in the order of the graph. 相似文献
18.
The boxicity of a graph H, denoted by , is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in Rk. In this paper we show that for a line graph G of a multigraph, , where Δ(G) denotes the maximum degree of G. Since G is a line graph, Δ(G)≤2(χ(G)−1), where χ(G) denotes the chromatic number of G, and therefore, . For the d-dimensional hypercube Qd, we prove that . The question of finding a nontrivial lower bound for was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795–5800].The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once). 相似文献
19.
We are interested in improving the Varshamov bound for finite values of length n and minimum distance d. We employ a counting lemma to this end which we find particularly useful in relation to Varshamov graphs. Since a Varshamov
graph consists of components corresponding to low weight vectors in the cosets of a code it is a useful tool when trying to
improve the estimates involved in the Varshamov bound. We consider how the graph can be iteratively constructed and using
our observations are able to achieve a reduction in the over-counting which occurs. This tightens the lower bound for any
choice of parameters n, k, d or q and is not dependent on information such as the weight distribution of a code.
This work is taken from the author’s thesis [10] 相似文献
20.
Andrzej Czygrinow Glenn Hurlbert H.A. Kierstead William T. Trotter 《Graphs and Combinatorics》2002,18(2):219-225
We say that a graph G is Class 0 if its pebbling number is exactly equal to its number of vertices. For a positive integer d, let k(d) denote the least positive integer so that every graph G with diameter at most d and connectivity at least k(d) is Class 0. The existence of the function k was conjectured by Clarke, Hochberg and Hurlbert, who showed that if the function k exists, then it must satisfy k(d)=Ω(2
d
/d). In this note, we show that k exists and satisfies k(d)=O(2
2d
). We also apply this result to improve the upper bound on the random graph threshold of the Class 0 property.
Received: April 19, 1999 Final version received: February 15, 2000 相似文献