Claw Conditions for Heavy Cycles in Weighted Graphs

A graph is called a weighted graph when each edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, d^w(v) is the sum of the weights of the edges incident with v. For a subgraph H of a weighted graph G, the weight of H is the sum of the weights of the edges belonging to H. In this paper, we give a new sufficient condition for a weighted graph to have a heavy cycle. A 2-connected weighted graph G contains either a Hamilton cycle or a cycle of weight at least c, if G satisfies the following conditions: In every induced claw or induced modified claw F of G, (1) max{d^w(x),d^w(y)} c/2 for each non-adjacent pair of vertices x and y in F, and (2) all edges of F have the same weight.     

A new sufficient condition for Hamiltonian graphs

The study of Hamiltonian graphs began with Dirac’s classic result in 1952. This was followed by that of Ore in 1960. In 1984 Fan generalized both these results with the following result: If G is a 2-connected graph of order n and max{d(u),d(v)}≥n/2 for each pair of vertices u and v with distance d(u,v)=2, then G is Hamiltonian. In 1991 Faudree–Gould–Jacobson–Lesnick proved that if G is a 2-connected graph and |N(u)∪N(v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is Hamiltonian. This paper generalizes the above results when G is 3-connected. We show that if G is a 3-connected graph of order n and max{|N(x)∪N(y)|+d(u),|N(w)∪N(z)|+d(v)}≥n for every choice of vertices x,y,u,w,z,v such that d(x,y)=d(y,u)=d(w,z)=d(z,v)=d(u,v)=2 and where x,y and u are three distinct vertices and w,z and v are also three distinct vertices (and possibly |{x,y}∩{w,z}| is 1 or 2), then G is Hamiltonian.     

Heavy cycles passing through some specified vertices in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex υ is called the weighted degree of υ. The weight of a cycle is defined as the sum of the weights of its edges. In this paper, we prove that: (1) if G is a 2‐connected weighted graph such that the minimum weighted degree of G is at least d, then for every given vertices x and y, either G contains a cycle of weight at least 2d passing through both of x and y or every heaviest cycle in G is a hamiltonian cycle, and (2) if G is a 2‐connected weighted graph such that the weighted degree sum of every pair of nonadjacent vertices is at least s, then for every vertex y, G contains either a cycle of weight at least s passing through y or a hamiltonian cycle. AMS classification: 05C45 05C38 05C35. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Computation of Topological Indices of Some Graphs

Let G=(V,E) be a simple connected graph with vertex set V and edge set E. The Wiener index of G is defined by W(G)=∑_{x,y}⊆V d(x,y), where d(x,y) is the length of the shortest path from x to y. The Szeged index of G is defined by Sz(G)=∑ _e=uv∈E n _u (e|G)n _v (e|G), where n _u (e|G) (resp. n _v (e|G)) is the number of vertices of G closer to u (resp. v) than v (resp. u). The Padmakar–Ivan index of G is defined by PI(G)=∑ _e=uv∈E [n _eu (e|G)+n _ev (e|G)], where n _eu (e|G) (resp. n _ev (e|G)) is the number of edges of G closer to u (resp. v) than v (resp. u). In this paper we find the above indices for various graphs using the group of automorphisms of G. This is an efficient method of finding these indices especially when the automorphism group of G has a few orbits on V or E. We also find the Wiener indices of a few graphs which frequently arise in mathematical chemistry using inductive methods.     

On the Existence of a Long Path Between Specified Vertices in a 2-Connected Graph

 Let G be a 2-connected graph with maximum degree Δ (G)≥d, and let x and y be distinct vertices of G. Let W be a subset of V(G)−{x, y} with cardinality at most d−1. Suppose that max{d _G(u), d _G(v)}≥d for every pair of vertices u and v in V(G)−({x, y}∪W) with d _G(u,v)=2. Then x and y are connected by a path of length at least d−|W|. Received: February 5, 1998 Revised: April 13, 1998     

List total colorings of series-parallel graphs

A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)|min{5,Δ+1} for each vertex v and |L(e)|max{5,d(v)+1,d(w)+1} for each edge e=vw, where Δ is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with Δ+1 colors if Δ4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition.     

Cycles in weighted graphs

A weighted graph is one in which each edgee is assigned a nonnegative numberw(e), called the weight ofe. The weightw(G) of a weighted graphG is the sum of the weights of its edges. In this paper, we prove, as conjectured in [2], that every 2-edge-connected weighted graph onn vertices contains a cycle of weight at least 2w(G)/(n–1). Furthermore, we completely characterize the 2-edge-connected weighted graphs onn vertices that contain no cycle of weight more than 2w(G)/(n–1). This generalizes, to weighted graphs, a classical result of Erds and Gallai [4].     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

Small alliances in a weighted graph

We extend the notion of a defensive alliance to weighted graphs. Let (G,w) be a weighted graph, where G is a graph and w be a function from V(G) to the set of positive real numbers. A non-empty set of vertices S in G is said to be a weighted defensive alliance if ∑_{x∈NG(v)∩S}w(x)+w(v)≥∑_{x∈NG(v)−S}w(x) holds for every vertex v in S. Fricke et al. (2003) [3] have proved that every graph of order n has a defensive alliance of order at most . In this note, we generalize this result to weighted defensive alliances. Let G be a graph of order n. Then we prove that for any weight function w on V(G), (G,w) has a defensive weighted alliance of order at most . We also extend the notion of strong defensive alliance to weighted graphs and generalize a result in Fricke et al. (2003) [3].     

T-Colorings and T-Edge Spans of Graphs

 Suppose G is a graph and T is a set of non-negative integers that contains 0. A T-coloring of G is an assignment of a non-negative integer f(x) to each vertex x of G such that |f(x)−f(y)|∉T whenever xy∈E(G). The edge span of a T-coloring−f is the maximum value of |f(x) f(y)| over all edges xy, and the T-edge span of a graph G is the minimum value of the edge span of a T-coloring of G. This paper studies the T-edge span of the dth power C ^d _n of the n-cycle C _n for T={0, 1, 2, …, k−1}. In particular, we find the exact value of the T-edge span of C _n ^d for n≡0 or (mod d+1), and lower and upper bounds for other cases. Received: May 13, 1996 Revised: December 8, 1997     

关于赋权图中重圈的一个范型定理

设G=(V, E; w)为赋权图,定义G中点v的权度d_G^w(v)为G中与v相关联的所有边的权和.该文证明了下述定理: 假设G为满足下列条件的2 -连通赋权图: (i) 对G中任何导出路xyz都有w(xy)=w(yz); (ii)对G中每一个与K_1,3或K_1,3+e同构的导出子图T, T中所有边的权都相等并且min{max{d_G^w(x), d^w_G(y)}:d(x,y)=2,x,y∈ V(T)}≥ c/2. 那么, G中存在哈密尔顿圈或者存在权和至少为 c 的圈. 该结论分别推广了Fan^[5], Bedrossian等人^[2]和Zhang等人^[7]的相关定理     

Triangle-free distance-regular graphs

Let Γ denote a distance-regular graph with diameter d≥3. By a parallelogram of length 3, we mean a 4-tuple xyzw consisting of vertices of Γ such that ∂(x,y)=∂(z,w)=1, ∂(x,z)=3, and ∂(x,w)=∂(y,w)=∂(y,z)=2, where ∂ denotes the path-length distance function. Assume that Γ has intersection numbers a ₁=0 and a ₂≠0. We prove that the following (i) and (ii) are equivalent. (i) Γ is Q-polynomial and contains no parallelograms of length 3; (ii) Γ has classical parameters (d,b,α,β) with b<−1. Furthermore, suppose that (i) and (ii) hold. We show that each of b(b+1)²(b+2)/c ₂, (b−2)(b−1)b(b+1)/(2+2b−c ₂) is an integer and that c ₂≤b(b+1). This upper bound for c ₂ is optimal, since the Hermitian forms graph Her₂(d) is a triangle-free distance-regular graph that satisfies c ₂=b(b+1). Work partially supported by the National Science Council of Taiwan, R.O.C.     

Path covers of weighted graphs

Let (G, w) denote a simple graph G with a weight function w : E(G) ← {0, 1, 2}. A path cover of (G, w) is a collection of paths in G such that every edge e is contained in exactly w(e) paths of the collection. For a vertex v, w(v) is the sum of the weights of the edges incident with v; v is called an odd (even) vertex if w(v) is odd (even). We prove that if every vertex of (G, w) is incident with at most one edge of weight 2, then (G, w) has a path cover P such that each odd vertex occurs exactly once, and each even vertex exactly twice, as an end of a path of P. We also prove that if every vertex of (G, w) is even, then (G, w) has a path cover P such that each vertex occurs exactly twice as an end of a path of P. © 1995 John Wiley & Sons, Inc.     

On a Max-min Problem Concerning Weights of Edges

The weight w(e) of an edge e = uv of a graph is defined to be the sum of degrees of the vertices u and v. In 1990 P. Erdős asked the question: What is the minimum weight of an edge of a graph G having n vertices and m edges? This paper brings a precise answer to the above question of Erdős. Received July 12, 1999     

The size-Ramsey number of trees

IfG andH are graphs, let us writeG→(H)₂ ifG contains a monochromatic copy ofH in any 2-colouring of the edges ofG. Thesize-Ramsey number r _e(H) of a graphH is the smallest possible number of edges a graphG may have ifG→(H)₂. SupposeT is a tree of order |T|≥2, and lett ₀,t ₁ be the cardinalities of the vertex classes ofT as a bipartite graph, and let Δ(T) be the maximal degree ofT. Moreover, let Δ₀, Δ₁ be the maxima of the degrees of the vertices in the respective vertex classes, and letβ(T)=T ₀Δ₀+t ₁Δ₁. Beck [7] proved thatβ(T)/4≤r _e(T)=O{β(T)(log|T|)¹²}, improving on a previous result of his [6] stating thatr _e(T)≤Δ(T)|T|(log|T|)¹². In [6], Beck conjectures thatr _e(T)=O{Δ(T)|T|}, and in [7] he puts forward the stronger conjecture thatr _e(T)=O{β(T)}. Here, we prove the first of these conjectures, and come quite close to proving the second by showing thatr _e(T)=O{β(T)logΔ(T)}.     

One sufficient condition for Hamiltonian graphs involving distances

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.     

Product irregularity strength of graphs

Consider a simple graph G with no isolated edges and at most one isolated vertex. A labeling w:E(G)→{1,2,…,m} is called product-irregular, if all product degrees pd_G(v)=∏_e∋vw(e) are distinct. The goal is to obtain a product-irregular labeling that minimizes the maximum label. This minimum value is called the product irregularity strength. The analogous concept of irregularity strength, with sums in place of products, has been introduced by Chartrand et al. and investigated by many authors.     

Google PageRanking problem: The model and the analysis

The spectral and Jordan structures of the Web hyperlink matrix G(c)=cG+(1−c)ev^T have been analyzed when G is the basic (stochastic) Google matrix, c is a real parameter such that 0<c<1, v is a nonnegative probability vector, and e is the all-ones vector. Typical studies have relied heavily on special properties of nonnegative, positive, and stochastic matrices. There is a unique nonnegative vector y(c) such that y(c)^TG(c)=y(c)^T and y(c)^Te=1. This PageRank vector y(c) can be computed effectively by the power method.We consider a square complex matrix A and nonzero complex vectors x and v such that Ax=λx and v^∗x=1. We use standard matrix analytic tools to determine the eigenvalues, the Jordan blocks, and a distinguished left λ-eigenvector of A(c)=cA+(1−c)λxv^∗ as a function of a complex variable c. If λ is a semisimple eigenvalue of A, there is a uniquely determined projection N such that lim_c→1y(c)=Nv for all v; this limit may fail to exist for some v if λ is not semisimple. As a special case of our results, we obtain a complex analog of PageRank for the Web hyperlink matrix G(c) with a complex parameter c. We study regularity, limits, expansions, and conditioning of y(c) and we propose algorithms (e.g., complex extrapolation, power method on a modified matrix etc.) that may provide an efficient way to compute PageRank also with c close or equal to 1. An interpretation of the limit vector Nv and a related critical discussion on the model, on its adherence to reality, and possible ways for its improvement, represent the contribution of the paper on modeling issues.     

A degree sum condition for longest cycles in 3‐connected graphs

For a graph G, we denote by d_G(x) and κ(G) the degree of a vertex x in G and the connectivity of G, respectively. In this article, we show that if G is a 3‐connected graph of order n such that d_G(x) + d_G(y) + d_G(z) ≥ d for every independent set {x, y, z}, then G contains a cycle of length at least min{d ? κ(G), n}. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 277–283, 2007     

Bounded Direction–Length Frameworks

A direction–length framework is a pair (G,p) where G=(V;D,L) is a ‘mixed’ graph whose edges are labelled as ‘direction’ or ‘length’ edges and p is a map from V to ℝ ^d for some d. The label of an edge uv represents a direction or length constraint between p(u) and p(v). Let G ⁺ be obtained from G by adding, for each length edge e of G, a direction edge with the same end vertices as e. We show that (G,p) is bounded if and only if (G ⁺,p) is infinitesimally rigid. This gives a characterization of when (G,p) is bounded in terms of the rank of the rigidity matrix of (G ⁺,p). We use this to characterize when a mixed graph is generically bounded in ℝ ^d . As an application we deduce that if (G,p) is a globally rigid generic framework with at least two length edges and e is a length edge of G then (G∖e,p) is bounded.