共查询到20条相似文献,搜索用时 31 毫秒
1.
In 1990 G. T. Chen proved that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x) + d(y) ≥ 2n − 1 for each pair of nonadjacent vertices x, y ∈ V (G), then G is Hamiltonian. In this paper we prove that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x)+d(y) ≥ 2n−1 for each pair of nonadjacent vertices x, y ∈ V (G) such that d(x, y) = 2, then G is Hamiltonian. 相似文献
2.
Guantao Chen Ronald J. Gould Michael S. Jacobson Richard H. Schelp 《Journal of Graph Theory》1994,18(7):663-672
For several years, the study of neighborhood unions of graphs has given rise to important structural consequences of graphs. In particular, neighborhood conditions that give rise to hamiltonian cycles have been considered in depth. In this paper we generalize these approaches to give a bound on the smallest number of cycles in G containing all the vertices of G. We show that if for all x, y ? V(G), |N(x) ∩ N(y)| ≧ 2n/5 + 1, then V(G) is coverable by at most two cycles. Several related results and extensions to t cycles are also given. 相似文献
3.
Ralph J. Faudree Ronald J. Gould Michael S. Jacobson Richard H. Schelp 《Journal of Graph Theory》1987,11(4):555-564
We examine several extremal problems for graphs satisfying the property |N(x) ∪ N(y)| ? s for every pair of nonadjacent vertices x, y ? V(G). In particular, values for s are found that ensure that the graph contains an s-matching, a 1-factor, a path of a specific length, or a cycle of a specific length. 相似文献
4.
It is well known that a graph G of order p ≥ 3 is Hamilton-connected if d(u) + d(v) ≥ p + 1 for each pair of nonadjacent vertices u and v. In this paper we consider connected graphs G of order at least 3 for which d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| + 1 for any path uwv with uv ∉ E(G), where N(x) denote the neighborhood of a vertex x. We prove that a graph G satisfying this condition has the following properties: (a) For each pair of nonadjacent vertices x, y of G and for each integer k, d(x, y) ≤ k ≤ |V(G)| − 1, there is an x − y path of length k. (b) For each edge xy of G and for each integer k (excepting maybe one k η {3,4}) there is a cycle of length k containing xy. Consequently G is panconnected (and also edge pancyclic) if and only if each edge of G belongs to a triangle and a quadrangle. Our results imply some results of Williamson, Faudree, and Schelp. © 1996 John Wiley & Sons, Inc. 相似文献
5.
Let G be a graph and S ⊂ V(G). We denote by α(S) the maximum number of pairwise nonadjacent vertices in S. For x, y ∈ V(G), the local connectivity κ(x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define . In this paper, we show that if κ(S) ≥ 3 and for every independent set {x
1, x
2, x
3, x
4} ⊂ S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian. 相似文献
6.
For x and y vertices of a connected graph G, let TG(x, y) denote the expected time before a random walk starting from x reaches y. We determine, for each n > 0, the n-vertex graph G and vertices x and y for which TG(x, y) is maximized. the extremal graph consists of a clique on ?(2n + 1)/3?) (or ?)(2n ? 2)/3?) vertices, including x, to which a path on the remaining vertices, ending in y, has been attached; the expected time TG(x, y) to reach y from x in this graph is approximately 4n3/27. 相似文献
7.
Xin Min Hou 《数学学报(英文版)》2012,28(11):2161-2168
A graph G satisfies the Ore-condition if d(x) + d(y) ≥ | V (G) | for any xy ■ E(G). Luo et al. [European J. Combin., 2008] characterized the simple Z3-connected graphs satisfying the Ore-condition. In this paper, we characterize the simple Z3-connected graphs G satisfying d(x) + d(y) ≥ | V (G) |-1 for any xy ■ E(G), which improves the results of Luo et al. 相似文献
8.
The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is the smallest number of such isolated vertices. Computing the competition number of a graph is an NP-hard problem in general and has been one of the important research problems in the study of competition graphs. Opsut [1982] showed that the competition number of a graph G is related to the edge clique cover number θ E (G) of the graph G via θ E (G) ? |V(G)| + 2 ≤ k(G) ≤ θ E (G). We first show that for any positive integer m satisfying 2 ≤ m ≤ |V(G)|, there exists a graph G with k(G) = θ E (G) ? |V(G)| + m and characterize a graph G satisfying k(G) = θ E (G). We then focus on what we call competitively tight graphs G which satisfy the lower bound, i.e., k(G) = θ E (G) ? |V(G)| + 2. We completely characterize the competitively tight graphs having at most two triangles. In addition, we provide a new upper bound for the competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight. 相似文献
9.
It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σx∈V(H) degG(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999 相似文献
10.
Vu-Dinh-Hoa 《Mathematische Nachrichten》1992,157(1):163-168
Let G be an undirected and simple graph on n vertices. Let ω, α and χ denote the number of components, the independence number and the connectivity number of G. G is called a 1-tough graph if ω(G – S) ? |S| for any subset S of V(G) such that ω(G ? S) > 1. Let σ2 = min {d(v) + d(w)|v and w are nonadjacent}. Note that the difference α - χ in 1-tough graph may be made arbitrary large. In this paper we prove that any 1-tough graph with σ2 > n + χ - α is hamiltonian. 相似文献
11.
We associate a graph 𝒩 G with a group G (called the non-nilpotent graph of G) as follows: take G as the vertex set and two vertices are adjacent if they generate a non-nilpotent subgroup. In this article, we study the graph theoretical properties of 𝒩 G and its induced subgraph on G \ nil(G), where nil(G) = {x ∈ G | ? x, y ? is nilpotent for all y ∈ G}. For any finite group G, we prove that 𝒩 G has either |Z*(G)| or |Z*(G)| +1 connected components, where Z*(G) is the hypercenter of G. We give a new characterization for finite nilpotent groups in terms of the non-nilpotent graph. In fact, we prove that a finite group G is nilpotent if and only if the set of vertex degrees of 𝒩 G has at most two elements. 相似文献
12.
Alan P Sprague 《Journal of Combinatorial Theory, Series B》1977,22(3):199-206
For any vertex x of a graph G let Δ(x) denote the set of vertices adjacent to x. We seek to describe the connected graphs G which are regular of valence n and in which for all adjacent vertices x and y |Δ(x) ∩ Δ(y)| = n ? 1 ? s. It is known that the complete graphs are the graphs for which s = 0. For any s, any complete many-partite graph, each part containing s + 1 vertices, is such a graph. We show that these are the only such graphs for which the valence exceeds 2s2 ? s + 1. The graphs satisfying these conditions for s = 1 or 2 are characterized (up to the class of trivalent triangle-free graphs.) 相似文献
13.
Anders Yeo 《Journal of Graph Theory》2007,55(4):325-337
A total dominating set, S, in a graph, G, has the property that every vertex in G is adjacent to a vertex in S. The total dominating number, γt(G) of a graph G is the size of a minimum total dominating set in G. Let G be a graph with no component of size one or two and with Δ(G) ≥ 3. In 6 , it was shown that |E(G)| ≤ Δ(G) (|V(G)|–γt(G)) and conjectured that |E(G)| ≤ (Δ(G)+3) (|V(G)|–γt(G))/2 holds. In this article, we prove that holds and that the above conjecture is false as there for every Δ exist Δ‐regular bipartite graphs G with |E(G)| ≥ (Δ+0.1 ln(Δ)) (|V(G)|–γt(G))/2. The last result also disproves a conjecture on domination numbers from 8 . © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 325–337, 2007 相似文献
14.
J.A. MacDougall 《Discrete Mathematics》2008,308(13):2756-2763
An edge-magic total labeling on G is a one-to-one map λ from V(G)∪E(G) onto the integers 1,2,…,|V(G)∪E(G)| with the property that, given any edge (x,y), λ(x)+λ(x,y)+λ(y)=k for some constant k. The labeling is strong if all the smallest labels are assigned to the vertices. Enomoto et al. proved that a graph admitting a strong labeling can have at most 2|V(G)|-3 edges. In this paper we study graphs of this maximum size. 相似文献
15.
A. S. Asratian H. J. Broersma J. Van den Heuvel H. J. Veldman 《Journal of Graph Theory》1996,21(1):1-10
For an integer i, a graph is called an Li-graph if, for each triple of vertices u, v, w with d(u, v) = 2 and w (element of) N(u) (intersection) N(v), d(u) + d(v) ≥ | N(u) (union) N(v) (union) N(w)| —i. Asratian and Khachatrian proved that connected Lo-graphs of order at least 3 are hamiltonian, thus improving Ore's Theorem. All K1,3-free graphs are L1-graphs, whence recognizing hamiltonian L1-graphs is an NP-complete problem. The following results about L1-graphs, unifying known results of Ore-type and known results on K1,3-free graphs, are obtained. Set K = lcub;G|Kp,p+1 (contained within) G (contained within) Kp V Kp+1 for some ρ ≥ } (v denotes join). If G is a 2-connected L1-graph, then G is 1-tough unless G (element of) K. Furthermore, if G is as connected L1-graph of order at least 3 such that |N(u) (intersection) N(v)| ≥ 2 for every pair of vertices u, v with d(u, v) = 2, then G is hamiltonian unless G ϵ K, and every pair of vertices x, y with d(x, y) ≥ 3 is connected by a Hamilton path. This result implies that of Asratian and Khachatrian. Finally, if G is a connected L1-graph of even order, then G has a perfect matching. © 1996 John Wiley & Sons, Inc. 相似文献
16.
A. Ainouche 《Journal of Graph Theory》1992,16(6):529-543
Let G be a k-connected graph of order n. For an independent set c, let d(S) be the number of vertices adjacent to at least one vertex of S and > let i(S) be the number of vertices adjacent to at least |S| vertices of S. We prove that if there exists some s, 1 ≤ s ≤ k, such that ΣxiEX d(X\{Xi}) > s(n?1) – k[s/2] – i(X)[(s?1)/2] holds for every independetn set X ={x0, x1 ?xs} of s + 1 vertices, then G is hamiltonian. Several known results, including Fraisse's sufficient condition for hamiltonian graphs, are dervied as corollaries. 相似文献
17.
Peter J. Slater 《Journal of Graph Theory》1978,2(3):209-222
For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize es(u) = max {d(u, v): v ∈ S} and ds(u) = ∑u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let rk(u) = max {∑s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which rk(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included. 相似文献
18.
Ladislav Nebeský 《Czechoslovak Mathematical Journal》2006,56(2):317-338
If G is a connected graph of order n ⩾ 1, then by a hamiltonian coloring of G we mean a mapping c of V (G) into the set of all positive integers such that |c(x) − c(y)| ⩾ n − 1 − D
G
(x, y) (where D
G
(x, y) denotes the length of a longest x − y path in G) for all distinct x, y ∈ V (G). Let G be a connected graph. By the hamiltonian chromatic number of G we mean
, where the minimum is taken over all hamiltonian colorings c of G.
The main result of this paper can be formulated as follows: Let G be a connected graph of order n ⩾ 3. Assume that there exists a subgraph F of G such that F is a hamiltonian-connected graph of order i, where 2 ⩽ i ⩽ 1/2 (n+1). Then hc(G) ⩽ (n−2)2+1−2(i−1)(i−2). 相似文献
19.
Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ? V{x\in V}. In the conditional covering problem, a vertex x ? V{x \in V} covers a vertex y ? V{y \in V} (x ≠ y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C í V{C\subseteq V} so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform
coverage radius in O(n
2) time, when G is an interval graph containing n vertices. 相似文献
20.
For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G. 相似文献