共查询到20条相似文献,搜索用时 31 毫秒
1.
One of the most fundamental results concerning paths in graphs is due to Ore: In a graph G, if deg x + deg y ≧ |V(G)| + 1 for all pairs of nonadjacent vertices x, y ? V(G), then G is hamiltonian-connected. We generalize this result using set degrees. That is, for S ? V(G), let deg S = |x?S N(x)|, where N(x) = {v|xv ? E(G)} is the neighborhood of x. In particular we show: In a 3-connected graph G, if deg S1 + deg S2 ≧ |V(G)| + 1 for each pair of distinct 2-sets of vertices S1, S2 ? V(G), then G is hamiltonian-connected. Several corollaries and related results are also discussed. 相似文献
2.
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. 相似文献
3.
Let G be a graph and W a subset of V(G). Let g,f:V(G)→Z be two integer-valued functions such that g(x)≤f(x) for all x∈V(G) and g(y)≡f(y) (mod 2) for all y∈W. Then a spanning subgraph F of G is called a partial parity (g,f)-factor with respect to W if g(x)≤deg
F
(x)≤f(x) for all x∈V(G) and deg
F
(y)≡f(y) (mod 2) for all y∈W. We obtain a criterion for a graph G to have a partial parity (g,f)-factor with respect to W. Furthermore, by making use of this criterion, we give some necessary and sufficient conditions for a graph G to have a subgraph which covers W and has a certain given property.
Received: June 14, 1999?Final version received: August 21, 2000 相似文献
4.
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. 相似文献
5.
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. 相似文献
6.
The average distance μ(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., μ(G) = ()−1 Σ{x,y}⊂V(G) dG(x, y), where V(G) denotes the vertex set of G and dG(x, y) is the distance between x and y. We prove that every connected graph of order n and minimum degree δ has a spanning tree T with average distance at most . We give improved bounds for K3‐free graphs, C4‐free graphs, and for graphs of given girth. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 1–13, 2000 相似文献
7.
John P. McSorley 《Discrete Mathematics》2008,308(23):5428-5445
For a simple graph G let NG(u) be the (open) neighborhood of vertex u∈V(G). Then G is neighborhood anti-Sperner (NAS) if for every u there is a v∈V(G)?{u} with NG(u)⊆NG(v). And a graph H is neighborhood distinct (ND) if every neighborhood is distinct, i.e., if NH(u)≠NH(v) when u≠v, for all u and v∈V(H).In Porter and Yucas [T.D. Porter, J.L. Yucas. Graphs whose vertex-neighborhoods are anti-sperner, Bulletin of the Institute of Combinatorics and its Applications 44 (2005) 69-77] a characterization of regular NAS graphs was given: ‘each regular NAS graph can be obtained from a host graph by replacing vertices by null graphs of appropriate sizes, and then joining these null graphs in a prescribed manner’. We extend this characterization to all NAS graphs, and give algorithms to construct all NAS graphs from host ND graphs. Then we find and classify all connected r-regular NAS graphs for r=0,1,…,6. 相似文献
8.
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. 相似文献
9.
A graph G is called quasi-claw-free if for any two vertices x and y with distance two there exists a vertex u∈N(x)∩N(y) such that N[u]⊆N[x]∪N[y]. This concept is a natural extension of the classical claw-free graphs. In this paper, we present two sufficient conditions for vertex pancyclicity in quasi-claw-free graphs, namely, quasilocally connected and almost locally connected graphs. Our results include some well-known results on claw-free graphs as special cases. We also give an affirmative answer to a problem proposed by Ainouche. 相似文献
10.
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. 相似文献
11.
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. 相似文献
12.
A Fan Type Condition For Heavy Cycles in Weighted Graphs 总被引:2,自引:0,他引:2
A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges. The weighted degree d
w
(v) of a vertex v is the sum of the weights of the edges incident with v. In this paper, we prove the following result: Suppose G is a 2-connected weighted graph which satisfies the following conditions: 1. max{d
w
(x),d
w
(y)∣d(x,y)=2}≥c/2; 2. w(x
z)=w(y
z) for every vertex z∈N(x)∩N(y) with d(x,y)=2; 3. In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains either a Hamilton cycle or a cycle of weight at least c. This generalizes a theorem of Fan on the existence of long cycles in unweighted graphs to weighted graphs. We also show
we cannot omit Condition 2 or 3 in the above result.
Received: February 7, 2000 Final version received: June 5, 2001 相似文献
13.
The nilpotent graph of a group G is a simple graph whose vertex set is G?nil(G), where nil(G) = {y ∈ G | ? x, y ? is nilpotent ? x ∈ G}, and two distinct vertices x and y are adjacent if ? x, y ? is nilpotent. In this article, we show that the collection of finite non-nilpotent groups whose nilpotent graphs have the same genus is finite, derive explicit formulas for the genus of the nilpotent graphs of some well-known classes of finite non-nilpotent groups, and determine all finite non-nilpotent groups whose nilpotent graphs are planar or toroidal. 相似文献
14.
. In this work we consider finite undirected simple graphs. If G=(V,E) is a graph we denote by α(G) the stability number of G. For any vertex x let N[x] be the union of x and the neighborhood N(x). For each pair of vertices ab of G we associate the set J(a,b) as follows. J(a,b)={u∈N[a]∩N[b]∣N(u)⊆N[a]∪N[b]}. Given a graph G, its partially squareG
* is the graph obtained by adding an edge uv for each pair u,v of vertices of G at distance 2 whenever J(u,v) is not empty. In the case G is a claw-free graph, G
* is equal to G
2.
If G is k-connected, we cover the vertices of G by at most ⌈α(G
*)/k⌉ cycles, where α(G
*) is the stability number of the partially square graph of G. On the other hand we consider in G
* conditions on the sum of the degrees. Let G be any 2-connected graph and t be any integer (t≥2). If ∑
x
∈
S
deg
G
(x)≥|G|, for every t-stable set S⊆V(G) of G
* then the vertex set of G can be covered with t−1 cycles. Different corollaries on covering by paths are given.
Received: January 22, 1997 Final version received: February 15, 2000 相似文献
15.
A graph G is bridged if every cycle C of length at least 4 has vertices x,y such that dG(x,y) < dC(x,y). A cycle C is isometric if dG(x,y) = dC(x,y) for all x,y ∈ V(C). We show that every graph contractible to a graph with girth g has an isometric cycle of length at least g. We use this to show that every minimal cutset S in a bridged graph G induces a connected subgraph. We introduce a “crowning” construction to enlarge bridged graphs. We use this to construct examples showing that for every connected simple graph H with girth at least 6 (including trees), there exists a bridged graph G such that G has a unique minimum cutset S and that G[S] = H. This provides counterexamples to Hahn's conjecture that dG(u,v) ≤ 2 when u and v lie in a minimum cutset in a bridged graph G. We also study the convexity of cutsets in bridged graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 161–170, 2003 相似文献
16.
Let G be a (V,E) graph of order p≥2. The double vertex graph U
2
(G) is the graph whose vertex set consists of all 2-subsets of V such that two distinct vertices {x,y} and {u,v} are adjacent if and only if |{x,y}∩{u,v}|=1 and if x=u, then y and v are adjacent in G. For this class of graphs we discuss the regularity, eulerian, hamiltonian, and bipartite properties of these graphs. A generalization
of this concept is n-tuple vertex graphs, defined in a manner similar to double vertex graphs. We also review several recent results for n-tuple vertex graphs.
Received: October, 2001 Final version received: September 20, 2002
Dedicated to Frank Harary on the occasion of his Eightieth Birthday and the Manila International Conference held in his honor 相似文献
17.
Pierre Fraisse 《Journal of Graph Theory》1986,10(4):553-557
Let G = (V, E) be a digraph of order n, satisfying Woodall's condition ? x, y ∈ V, if (x, y) ? E, then d+(x) + d?(y) ≥ n. Let S be a subset of V of cardinality s. Then there exists a circuit including S and of length at most Min(n, 2s). In the case of oriented graphs we obtain the same result under the weaker condition d+(x) + d?(y) ≥ n – 2 (which implies hamiltonism). 相似文献
18.
Yoko Hasegawa 《Discrete Mathematics》2007,307(14):1801-1807
For a pair of vertices x and y in a graph G, we denote by dG(x,y) the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and dG(y,v)?dG(y,x) for each neighbor v of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by B(G).In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, |B(G)|?2 for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of |B(G)|. 相似文献
19.
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. 相似文献
20.
Norbert Polat 《Journal of Graph Theory》2003,43(4):280-298
A (finite or infinite) graph G is constructible if there exists a well‐ordering ≤ of its vertices such that for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Particular constructible graphs are Helly graphs and connected bridged graphs. In this paper we study a new class of constructible graphs, the class of locally Helly graphs. A graph G is locally Helly if, for every pair (x,y) of vertices of G whose distance is d ≥ 2, there exists a vertex whose distance to x is d ? 1 and which is adjacent to y and to all neighbors of y whose distance to x is at most d. Helly graphs are locally Helly, and the converse holds for finite graphs. Among different properties we prove that a locally Helly graph is strongly dismantable, hence cop‐win, if and only if it contains no isometric rays. We show that a locally Helly graph G is finitely Helly, that is, every finite family of pairwise non‐disjoint balls of G has a non‐empty intersection. We give a sufficient condition by forbidden subgraphs so that the three concepts of Helly graphs, of locally Helly graphs and of finitely Helly graphs are equivalent. Finally, generalizing different results, in particular those of Bandelt and Chepoi 1 about Helly graphs and bridged graphs, we prove that the Helly number h(G) of the geodesic convexity in a constructible graph G is equal to its clique number ω(G), provided that ω(G) is finite. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 280–298, 2003 相似文献