Circuits including a given set of vertices

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).     

Near automorphisms of cycles

Let f be a permutation of V(G). Define δ_f(x,y)=|d_G(x,y)-d_G(f(x),f(y))| and δ_f(G)=∑δ_f(x,y) over all the unordered pairs {x,y} of distinct vertices of G. Let π(G) denote the smallest positive value of δ_f(G) among all the permutations f of V(G). The permutation f with δ_f(G)=π(G) is called a near automorphism of G. In this paper, we study the near automorphisms of cycles C_n and we prove that π(C_n)=4⌊n/2⌋-4, moreover, we obtain the set of near automorphisms of C_n.     

(m)-covering of a triangulation

Let G be a graph triangularly imbedded into a surface S, G_(m) is the graph constructed from G by replacing each vertex x by m vertices (xx,0), (x, 1), ..., (x, m − 1) and joining two vertices (x, i) and (y, j) by an edge if and only if x and y are joined in G. The main result is that the construction of G_(m) is possible whenever n is an odd prime and a well separating cycle (mod m) can be determined.     

Degree sum and nowhere-zero 3-flows

Let G be a simple graph on n vertices. In this paper, we prove that if G satisfies the condition that d(x)+d(y)≥n for each xy∈E(G), then G has no nowhere-zero 3-flow if and only if G is either one of the five graphs on at most 6 vertices or one of a very special class of graphs on at least 6 vertices.     

Sur les arborescences dans un graphe oriente

The main result of this paper is the following theorem: Let G = (X,E) be a digraph without loops or multiple edges, |X| ?3, and h be an integer ?1, if G contains a spanning arborescence and if d⁺_G(x)+d^?_G(x)+d^?_G(y)+d^?_G(y)? 2|X |?2h?1 for all x, y?X, x ≠ y, non adjacent in G, then G contains a spanning arborescence with ?h terminal vertices. A strengthening of Gallai-Milgram's theorem is also proved.     

Distance matrix polynomials of trees

Let G be a finite connected graph. If x and y are vertices of G, one may define a distance function d_G on G by letting d_G(x, y) be the minimal length of any path between x and y in G (with d_G(x, x) = 0). Thus, for example, d_G(x, y) = 1 if and only if {x, y} is an edge of G. Furthermore, we define the distance matrix D(G) for G to be the square matrix with rows and columns indexed by the vertex set of G which has d_G(x, y) as its (x, y) entry. In this paper we are concerned with properties of D(G) for the case in which G is a tree (i.e., G is acyclic). In particular, we precisely determine the coefficients of the characteristic polynomial of D(G). This determination is made by deriving surprisingly simple expressions for these coefficients as certain fixed linear combinations of the numbers of various subgraphs of G.     

Engel type identities with derivations for right ideals in prime rings

Let R be a prime ring of char R≠2, d a non-zero derivation of R and ρ a non-zero right ideal of R such that [[d(x),d(y)]_n [y,x]_m] = 0 for all x,y ∈ ρ or [[d(x),d(y)]_n d[y,x]_m] = 0 for all x,y ∈ ρ, n, m ≥ 0 are fixed integers. If [ρ,ρ]ρ ≠ 0, then d(ρ)ρ = 0.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

A note on Z 3-connected graphs with degree sum condition

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.     

Ordering connected graphs having small degree distances

The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D^′(G)=∑_x∈V(G)d(x)∑_y∈V(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K_1,n−1,BS(n−3,1) and K_1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K_1,n−3 and K_1,1 with central vertices joined by an edge.     

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.     

Sphere coverings and identifying codes

In any connected, undirected graph G = (V, E), the distance d(x, y) between two vertices x and y of G is the minimum number of edges in a path linking x to y in G. A sphere in G is a set of the form S _r (x) = {y ∈ V : d(x, y) = r}, where x is a vertex and r is a nonnegative integer called the radius of the sphere. We first address in this paper the following question: What is the minimum number of spheres with fixed radius r ≥ 0 required to cover all the vertices of a finite, connected, undirected graph G? We then turn our attention to the Hamming Hypercube of dimension n, and we show that the minimum number of spheres with any radii required to cover this graph is either n or n + 1, depending on the parity of n. We also relate the two above problems to other questions in combinatorics, in particular to identifying codes.     

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     

Super-vertex-antimagic total labelings of disconnected graphs

Let G=(V,E) be a finite, simple and non-empty (p,q)-graph of order p and size q. An (a,d)-vertex-antimagic total labeling is a bijection f from V(G)∪E(G) onto the set of consecutive integers 1,2,…,p+q, such that the vertex-weights form an arithmetic progression with the initial term a and the common difference d, where the vertex-weight of x is the sum of values f(xy) assigned to all edges xy incident to vertex x together with the value assigned to x itself, i.e. f(x). Such a labeling is called super if the smallest possible labels appear on the vertices.In this paper, we will study the properties of such labelings and examine their existence for disconnected graphs.     

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     

Characterization of a class of bivariate distribution functions

Let F_X,Y(x,y) be a bivariate distribution function and P_n(x), Q_m(y), n, m = 0, 1, 2,…, the orthonormal polynomials of the two marginal distributions F_X(x) and F_Y(y), respectively. Some necessary conditions are derived for the co-efficients c_n, n = 0, 1, 2,…, if the conditional expectation E[P_n(X) ∥ Y] = c_nQ_n(Y) holds for n = 0, 1, 2,…. Several examples are given to show the application of these necessary conditions.     

The strong chromatic index of a class of graphs

The strong chromatic index of a graph G is the minimum integer k such that the edge set of G can be partitioned into k induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211] proposed an open problem: If G is bipartite and if for each edge xy∈E(G), d(x)+d(y)≤5, then sχ^′(G)≤6. Let H₀ be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if G (not necessarily bipartite) is not isomorphic to H₀ and d(x)+d(y)≤5 for any edge xy of G then sχ^′(G)≤6. The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs.