The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius

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 ²) time, when G is an interval graph containing n vertices.     

Fan-type theorem for path-connectivity

A graphG is said to bek-path-connected if every pair of distinct vertices inG are joined by a path of length at leastk. We prove that if max{deg _G ^x , deg _G ^y }k for every pair of verticesx,y withd _G (x,y)=2 in a 2-connected graphG, whered _G (x,y) is the distance betweenx andy inG, thenG isk-path-connected.     

Average distance,minimum degree,and spanning trees

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) = ()⁻¹ Σ_{x,y}⊂V(G) d_G(x, y), where V(G) denotes the vertex set of G and d_G(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 K₃‐free graphs, C₄‐free graphs, and for graphs of given girth. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 1–13, 2000     

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.     

A Degree Sum Condition Concerning the Connectivity and the Independence Number of a Graph

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 ₁, x ₂, x ₃, x ₄} ⊂ 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.     

The w-median of a connected strongly chordal graph

Suppose G = (V, E) is a graph in which every vertex x has a non-negative real number w(x) as its weight. The w-distance sum of a vertex y is D_{G, w}(y) = σ_x?v d(y, x)w(x). The w-median of G is the set of all vertices y with minimum w-distance sum D_G,w(y). This paper shows that the w-median of a connected strongly chordal graph G is a clique when w(x) is positive for all vertices x in G.     

Vertex pancyclicity and new sufficient conditions

For a graph G, ??(G) denotes the minimum degree of G. In 1971, Bondy proved that, if G is a 2-connected graph of order n and d(x)?+?d(y)????n for each pair of non-adjacent vertices x,y in G, then G is pancyclic or G?=?K _n/2,n/2. In 2001, Xu proved that, if G is a 2-connected graph of order n????6 and |N(x)????N(y)|?+???(G)????n for each pair of non-adjacent vertices x,y in G, then G is pancyclic or G?=?K _n/2,n/2. In this paper, we introduce a new sufficient condition of generalizing degree sum and neighborhood union and prove that, if G is a 2-connected graph of order n????6 and |N(x)????N(y)|?+?d(w)????n for any three vertices x,y,w of d(x,y)?=?2 and wx or $wy\not\in E(G)$ in G, then G is 4-vertex pancyclic or G belongs to two classes of well-structured exceptional graphs. This result also generalizes the above results.     

The ratio of the distance irredundance and domination numbers of a graph

Let n ≥ 1 be an integer and let G be a graph. A set D of vertices in G is defined to be an n-dominating set of G if every vertex of G is within distance n from some vertex of D. The minimum cardinality among all n-dominating sets of G is called the n-domination number of G and is denoted by γ_n(G). A set / of vertices in G is n-irredundant if for every vertex x ∈ / there exists a vertex y that is within distance n from x but at distance greater than n from every vertex of / - {x}. The n-irredundance number of G, denoted by ir_n(G), is the minimum cardinality taken over all maximal n-irredundant sets of vertices of G. We show that inf{ir_n(G)/γ_n(G) | G is an arbitrary finite undirected graph with neither loops nor multiple edges} = 1/2 with the infimum not being attained. Subsequently, we show that 2/3 is a lower bound on all quotients ir_n(T)/γ_n(T) in which T is a tree. Furthermore, we show that, for n ≥ 2, this bound is sharp. These results extend those of R. B. Allan and R.C. Laskar [“On Domination and Some Related Concepts in Graph Theory,” Utilitas Mathematica, Vol. 21 (1978), pp. 43–56], B. Bollobás and E. J. Cockayne [“Graph-Theoretic Parameters Concerning Domination, Independence and Irredundance,” Journal of Graph Theory, Vol. 3 (1979), pp. 241–249], and P. Damaschke [Irredundance Number versus Domination Number, Discrete Mathematics, Vol. 89 (1991), pp. 101–104].     

Inequalities for Means in Two Variables

We present various new inequalities involving the logarithmic mean L(x,y)=(x-y)/(logx-logy) L(x,y)=(x-y)/(\log{x}-\log{y}) , the identric mean I(x,y)=(1/e)(x^x/y^y)^1/(x-y) I(x,y)=(1/e)(x^x/y^y)^{1/(x-y)} , and the classical arithmetic and geometric means, A(x,y)=(x+y)/2 A(x,y)=(x+y)/2 and G(x,y)=?{xy} G(x,y)=\sqrt{xy} . In particular, we prove the following conjecture, which was published in 1986 in this journal. If M_r(x,y) = (x^r/2+y^r/2)^1/r(r 1 0) M_r(x,y)= (x^r/2+y^r/2)^{1/r}(r\neq{0}) denotes the power mean of order r, then $ M_c(x,y)<\frac{1}{2}(L(x,y)+I(x,y)) {(x,y>0,\, x\neq{y})} $ M_c(x,y)<\frac{1}{2}(L(x,y)+I(x,y)) {(x,y>0,\, x\neq{y})} with the best possible parameter c=(log2)/(1+log2) c=(\log{2})/(1+\log{2}) .     

Some Algebraic Methods for Calculating the Number of Colorings of a Graph

With an arbitrary graph G having n vertices and m edges, and with an arbitrary natural number p, we associate in a natural way a polynomial R(x ₁,...,x _n) with integer coefficients such that the number of colorings of the vertices of the graph G in p colors is equal to p ^m-n R(0,...,0). Also with an arbitrary maximal planar graph G, we associate several polynomials with integer coefficients such that the number of colorings of the edges of the graph G in 3 colors can be calculated in several ways via the coefficients of each of these polynomials. Bibliography: 2 titles.     

On hamiltonian-connected graphs

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 S₁ + deg S₂ ≧ |V(G)| + 1 for each pair of distinct 2-sets of vertices S₁, S₂ ? V(G), then G is hamiltonian-connected. Several corollaries and related results are also discussed.     

Diameters of finite upper half plane graphs

Let GF(q) be a finite field of q elements. Let G denote the group of matrices M(x, y) = (^{y x}_{0 1}) over GF(q) with y ≠ 0. Fix an irreducible polynomial For each a ϵ GF(q), let X_a be the graph whose vertices are the q² − q elements of G, with two vertices M(x, y), M(v, w) joined by an edge if and only if The graphs X_a with a ϵ/ {0, t² − 4n} are (q + 1)-regular connected graphs which have received recent attention, as they've been shown to be Ramanujan graphs. We determine the diameter of these graphs X_a. © 1996 John Wiley & Sons, Inc.     

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     

Induced matching extendable graphs

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K₂, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are C_n × K₂, for n ≥ 3, and C_2n(1, n), for n ≥ 2, where C_2n(1, n) is the graph with 2n vertices x₀, x₁, …, x_2n−1, such that x_ix_j is an edge of C_2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998     

The 2-hamiltonian cubes of graphs

This paper deals with the problem of characterizing the pairs of vertices x,y in a connected graph G such that G³ - {x,y} is hamiltonian, where G³ is the cube of G. It is known that the cube G³ is 2-hamiltonian if G is 2-connected. In this paper, we first prove the stronger result that G³ - {x,y} is hamiltonian if either x or y is not a cut-vertex of G, and then proceed to characterize those cut-vertices x and y of G such that G³ -{x,y} is hamiltonian. As a simple consequence of these, we obtain Schaar's characterization of a connected graph G such that G³ is 2-hamiltonian.     

Realization of digraphs by preferences based on distances in graphs

Consider a graph G with two distinguished sets of vertices: the voters and the candidates. A voter v prefers candidate x to candidate y if d(v, x) < d(v, y). This preference relation defines an asymmetric digraph whose vertices are the candidates, in which there is an arc from candidate x to candidate y if and only if more voters prefer x to y than prefer y to x. T. W. Johnson and P. J. Slater (“Realization of Majority Preference Digraphs by Graphically Determined Voting Patterns,” Congressus Numerantium, vol. 67 [1988] 175-186) have shown that each asymmetric digraph of order n can be realized in this way using a graph of order O(n²). We present a new construction reducing the quadratic upper bound to a linear bound. © 1995 John Wiley & Sons, Inc.     

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.     

On exponential sums over primes in short intervals

Let Λ(n) be the von Mangoldt function, x real and y small compared with x. This paper gives a non-trivial estimate on the exponential sum over primes in short intervals S₂(x,y;a)=?_{x < n ￡ x+y}L(n)e(n² a)S_2(x,y;{\alpha})=\sum_{x < n \le x+y}\Lambda(n)e(n^2 {\alpha}) for all α ∈ [0,1] whenever x^\frac23+e ￡ y ￡ xx^{\frac{2}{3}+{\varepsilon}}\le y \le x . This result is as good as what was previously derived from the Generalized Riemann Hypothesis.     

Graphs with small boundary

For a pair of vertices x and y in a graph G, we denote by d_G(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 d_G(y,v)?d_G(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)|.     

An Extremal Problem on Degree Sequences of Graphs

 Let G=(I _n ,E) be the graph of the n-dimensional cube. Namely, I _n ={0,1} ⁿ and [x,y]∈E whenever ||x−y||₁=1. For A⊆I _n and x∈A define h _A (x) =#{y∈I _n A|[x,y]∈E}, i.e., the number of vertices adjacent to x outside of A. Talagrand, following Margulis, proves that for every set A⊆I _n of size 2 ⁿ⁻¹ we have for a universal constant K independent of n. We prove a related lower bound for graphs: Let G=(V,E) be a graph with . Then , where d(x) is the degree of x. Equality occurs for the clique on k vertices. Received: January 7, 2000 RID="*" ID="*" Supported in part by BSF and by the Israeli academy of sciences