Spectra of Extended Double Cover Graphs

The construction of the extended double cover was introduced by N. Alon [1] in 1986. For a simple graph G with vertex set V = {v ₁, v ₂, ..., v _n }, the extended double cover of G, denoted G ^*, is the bipartite graph with bipartition (X, Y) where X = {x ₁, x ₂, ..., x _n } and Y = {y ₁, y ₂, ..., y _n }, in which x _i and y _j are adjacent iff i = j or v _i and v _j are adjacent in G.In this paper we obtain formulas for the characteristic polynomial and the spectrum of G ^* in terms of the corresponding information of G. Three formulas are derived for the number of spanning trees in G ^* for a connected regular graph G. We show that while the extended double covers of cospectral graphs are cospectral, the converse does not hold. Some results on the spectra of the nth iterared double cover are also presented.     

A note on on-line ranking number of graphs

A k-ranking of a graph G = (V, E) is a mapping ϕ: V → {1, 2, ..., k} such that each path with end vertices of the same colour c contains an internal vertex with colour greater than c. The ranking number of a graph G is the smallest positive integer k admitting a k-ranking of G. In the on-line version of the problem, the vertices v ₁, v ², ..., v _n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G[{v ₁, v ₂, ..., v _i }] are known when the colour for the vertex v _i has to be chosen. The on-line ranking number of a graph G is the smallest positive integer k such that there exists an algorithm that produces a k-ranking of G for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete n-partite graphs. The question of additivity and heredity is discussed as well.     

Partition conditions and vertex-connectivity of graphs

It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev ₁, ...,v _n ≠V(G) and for any sequence of positive integersk ₁, ...,k _n such thatk ₁+...+k _n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv ₁, ...,v(n), and the class of the partition containingv _i induces a connected subgraph consisting ofk _i vertices, fori=1, 2, ...,n. Now fix the integersk ₁, ...,k _n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv ₁, ...,v _n ≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.     

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.     

Mixed covering arrays on graphs

Covering arrays have applications in software, network and circuit testing. In this article, we consider a generalization of covering arrays that allows mixed alphabet sizes as well as a graph structure that specifies the pairwise interactions that need to be tested. Let k and n be positive integers, and let G be a graph with k vertices v₁,v₂,…, v_k with respective vertex weights g₁ ≤ g₂ ≤ … ≤ g_k. A mixed covering array on G, denoted by , is an n × k array such that column i corresponds to v_i, cells in column i are filled with elements from ?_gi and every pair of columns i,j corresponding to an edge v_i,v_j in G has every possible pair from ?_gi × ?_gj appearing in some row. The number of rows in such array is called its size. Given a weighted graph G, a mixed covering array on G with minimum size is called optimal. In this article, we give upper and lower bounds on the size of mixed covering arrays on graphs based on graph homomorphisms. We provide constructions for covering arrays on graphs based on basic graph operations. In particular, we construct optimal mixed covering arrays on trees, cycles and bipartite graphs; the constructed optimal objects have the additional property of being nearly point balanced. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 393–404, 2007     

Graph decompositions without isolated vertices III

Let G be a graph of order n, and n = Σ^k_i=1 a_i be a partition of n with a_i ≥ 2. In this article we show that if the minimum degree of G is at least 3k−2, then for any distinct k vertices v₁,…, v_k of G, the vertex set V(G) can be decomposed into k disjoint subsets A₁,…, A_k so that |A_i| = a_i,v_iisA_i is an element of A_i and “the subgraph induced by A_i contains no isolated vertices” for all i, 1 ≥ i ≥ k. Here, the bound on the minimum degree is sharp. © 1997 John Wiley & Sons, Inc.     

Bipartite Graphs Whose Edge Algebras Are Complete Intersections

Let R be a monomial subalgebra of k[x₁,…,x_N] generated by square free monomials of degree two. This paper addresses the following question: when is R a complete intersection? For such a k-algebra we can associate a graph G whose vertices are x₁,…,x_N and whose edges are {(x_i, x_j)|x_ix_j  R}. Conversely, for any graph G with vertices {x₁,…,x_N} we define the edge algebra associated with G as the subalgebra of k[x₁,…,x_N] generated by the monomials {x_ix_j|(x_i, x_j) is an edge of G}. We denote this monomial algebra by k[G]. This paper describes all bipartite graphs whose edge algebras are complete intersections.     

Some graft transformations and its applications on the distance spectral radius of a graph

Let D(G)=(d_i,j)_n×n denote the distance matrix of a connected graph G with order n, where d_ij is equal to the distance between v_i and v_j in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, some graft transformations that decrease or increase ?(G) are given. With them, for the graphs with both order n and k pendant vertices, the extremal graphs with the minimum distance spectral radius are completely characterized; the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph (obtained by attaching some pendant edges to each pendant vertex of a path respectively) when 2≤k≤n−2; for k=1,2,3,n−1, the extremal graphs with the maximum distance spectral radius are completely characterized.     

Sphere and Dot Product Representations of Graphs

A graph G is a k-sphere graph if there are k-dimensional real vectors v ₁,…,v _n such that ij∈E(G) if and only if the distance between v _i and v _j is at most 1. A graph G is a k-dot product graph if there are k-dimensional real vectors v ₁,…,v _n such that ij∈E(G) if and only if the dot product of v _i and v _j is at least 1.     

Orientations of circle graphs

Let C(v₁, …,v_n) be a system consisting of a circle C with chords v₁, …,v_n on it having different endpoints. Define a graph G having vertex set V(G) = {v₁, …,v_n} and for which vertices v_i and v_j are adjacent in G if the chords v_i and v_j intersect. Such a graph will be called a circle graph. The chords divide the interior of C into a number of regions. We give a method which associates to each such region an orientation of the edges of G. For a given C(v₁, …,v_n) the number m of different orientations corresponding to it satisfies q + 1 ≤ m ≤ n + q + 1, where q is the number of edges in G. An oriented graph obtained from a diagram C(v₁, …,v_n) as above is called an oriented circle graph (OCG). We show that transitive orientations of permutation graphs are OCGs, and give a characterization of tournaments which are OCGs. When the region is a peripheral one, the orientation of G is acyclic. In this case we define a special orientation of the complement of G, and use this to develop an improved algorithm for finding a maximum independent set in G.     

More rotation numbers for complete bipartite graphs

Let G be a simple undirected graph which has p vertices and is rooted at x. Informally, the rotation number h(G, x) of this rooted graph is the minimum number of edges in a p vertex graph H such that for each vertex v of H, there exists a copy of G in H with the root x at v. In this article we calculate some rotation numbers for complete bipartite graphs, and thus greatly extend earlier results of Cockayne and Lorimer.     

Balancing vectors in the max norm

Let v₁, ..., v _n be vectors inR ⁿ of max norm at most one. It is proven that there exists a choice of signs for which all partial sums have max norm at mostKn ^1/2. It is further shown that such a choice of signs must be anticipatory—there is no way to choose thei-th sign without knowledge of v _j forj>i.     

Regularity of Rees Algebras

Let B = k[x₁, ..., x_n] be a polynomial ring over a field k,and let A be a quotient ring of B by a homogeneous ideal J.Let m denote the maximal graded ideal of A. Then the Rees algebraR = A[m t] also has a presentation as a quotient ring of thepolynomial ring k[x₁, ..., x_n, y₁, ..., y_n] by a homogeneousideal J^*. For instance, if A = k[x₁, ..., x_n], then Rk[x₁,...,x_n,y₁,...,y_n]/(x_iy_j–x_jy_i|i, j=1,...,n). In this paper we want to compare the homological propertiesof the homogeneous ideals J and J^*.     

(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 sequences of graphs containing a cycle with prescribed length

Let r ≥ 3, n ≥ r and π = (d ₁, d ₂, ..., d _n ) be a non-increasing sequence of nonnegative integers. If π has a realization G with vertex set V (G) = {v ₁, v ₂, ..., v _n } such that d _G (v _i ) = d _i for i = 1, 2, ..., n and v ₁ v ₂ ... v _r v ₁ is a cycle of length r in G, then π is said to be potentially C _r ″-graphic. In this paper, we give a characterization for π to be potentially C _r ″-graphic. This work was supported by the grant of National Natural Science Foundation of China No. 10861006 and China Scholarship Council.     

Survey of Double Vertex Graphs

 Let G be a (V,E) graph of order p≥2. The double vertex graph U ₂ (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     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u ₁ = v ₁, v = u _v(G) = v _v(G) , and u _i ≠ v _i for every 1 < i < v(G). A set of hamiltonian paths, {P ₁, P ₂, . . . , P _k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n–k ≥ 2. We use S _n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S _n,k ) = n–2 except for S _4,2 such that IHP(S _4,2) = 1.      

Mutually orthogonal graph squares

A decomposition ??={G₁, G₂,…,G_s} of a graph G is a partition of the edge set of G into edge‐disjoint subgraphs G₁, G₂,…,G_s. If G_i?H for all i∈{1, 2, …, s}, then ?? is a decomposition of G by H. Two decompositions ??={G₁, G₂, …, G_n} and ?={F₁, F₂,…,F_n} of the complete bipartite graph K_n,n are orthogonal if |E(G_i)∩E(F_j)|=1 for all i,j∈{1, 2, …, n}. A set of decompositions {??₁, ??₂, …, ??_k} of K_{n, n} is a set of k mutually orthogonal graph squares (MOGS) if ??_i and ??_j are orthogonal for all i, j∈{1, 2, …, k} and i≠j. For any bipartite graph G with n edges, N(n, G) denotes the maximum number k in a largest possible set {??₁, ??₂, …, ??_k} of MOGS of K_{n, n} by G. El‐Shanawany conjectured that if p is a prime number, then N(p, P_{p+ 1})=p, where P_{p+ 1} is the path on p+ 1 vertices. In this article, we prove this conjecture. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 369–373, 2009