On computing minimal realizable spectral radii of non‐negative matrices

For decades considerable efforts have been exerted to resolve the inverse eigenvalue problem for non‐negative matrices. Yet fundamental issues such as the theory of existence and the practice of computation remain open. Recently, it has been proved that, given an arbitrary (n–1)‐tuple ?? = (λ₂,…,λ_n) ∈ ?^n–1 whose components are closed under complex conjugation, there exists a unique positive real number ?(??), called the minimal realizable spectral radius of ??, such that the set {λ₁,…,λ_n} is precisely the spectrum of a certain n × n non‐negative matrix with λ₁ as its spectral radius if and only if λ₁ ? ?(??). Employing any existing necessary conditions as a mode of checking criteria, this paper proposes a simple bisection procedure to approximate the location of ?(??). As an immediate application, it offers a quick numerical way to check whether a given n‐tuple could be the spectrum of a certain non‐negative matrix. Copyright © 2004 John Wiley & Sons, Ltd.     

Further results on the lower bounds of mean color numbers

Let G be a graph with n vertices. The mean color number of G, denoted by μ(G), is the average number of colors used in all n‐colorings of G. This paper proves that μ(G) ≥ μ(Q), where Q is any 2‐tree with n vertices and G is any graph whose vertex set has an ordering x₁,x₂,…,x_n such that x_i is contained in a K₃ of G[V_i] for i = 3,4,…,n, where V_i = {x₁,x₂,…,x_i}. This result improves two known results that μ(G) ≥ μ(O_n) where O_n is the empty graph with n vertices, and μ(G) ≥ μ(T) where T is a spanning tree of G. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 51–73, 2005     

Spectra of Cayley graphs

By a result of L. Lovász, the determination of the spectrum of any graph with transitive automorphism group easily reduces to that of some Cayley graph.We derive an expression for the spectrum of the Cayley graph X(G,H) in terms of irreducible characters of the group G:

for any natural number t, where ξ_i is an irreducible character (over $\text{C}$), of degree n_i , and λ_i,1 ,…, λ_i,ni are eigenvalues of X(G, H), each one n_i times. (σn_i² = n = | G | is the total'number of eigenvalues.) Using this formula for t = 1,…, n_i one can obtain a polynomial of degree n_i whose roots are λ_i,1,…,λ_i,ni. The results are formulated for directed graphs with colored edges. We apply the results to dihedral groups and prove the existence of k nonisomorphic Cayley graphs of D_p with the same spectrum provided p > 64k, prime.     

On the number of complementary trees in a graph

Consider a graph with no loops or multiple arcs with n+1 nodes and 2n arcs labeled a_l,…,a_n,a′_l,…,a′_n, where n ≥ 5. A spanning tree of such a graph is called complementary if it contains exactly one arc of each pair {a_i,a′_i}. The purpose of this paper is to develop a procedure for finding complementary trees in a graph, given one such tree. Using the procedure repeatedly we give a constructive proof that every graph of the above form which has one complementary tree has at least six such trees.     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Large set of P3‐decompositions

Let G=(V(G),E(G)) be a graph. A (n,G, λ)‐GD is a partition of the edges of λK_n into subgraphs (G‐blocks), each of which is isomorphic to G. The (n,G,λ)‐GD is named as graph design for G or G‐decomposition. The large set of (n,G,λ)‐GD is denoted by (n,G,λ)‐LGD. In this work, we obtain the existence spectrum of (n,P₃,λ)‐LGD. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 151–159, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10008     

Tail bounds for the height and width of a random tree with a given degree sequence

Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}Fix a sequence c = (c₁,…,c_n) of non‐negative integers with sum n ? 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let ${\mathcal T}$ be a plane tree drawn uniformly at random from among all plane trees with child sequence c . In this note we prove sub‐Gaussian tail bounds on the height (greatest depth of any node) and width (greatest number of nodes at any single depth) of ${\mathcal T}$. These bounds are optimal up to the constant in the exponent when c satisfies $\sum_{i=1}^n c_i^2=O(n)$; the latter can be viewed as a “finite variance” condition for the child sequence. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

Multicolored trees in complete graphs

A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K_2n(n > 2) with 2n ? 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a₁,…, a_k) is a color distribution for the complete graph K_n, n ≥ 5, such that , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph K_n with the above distribution if T is a non‐star multicolored spanning tree of K_n, then there exists a multicolored spanning tree T' of K_n such that T and T' are edge‐disjoint. Also it is shown that if K_n, n ≥ 6, is edge colored with k colors and , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007     

Conservative graphs

A graph G with q edges is defined to be conservative if the edges of G can be oriented and distinctly numbered with the integers 1, 2,…, q so that at each vertex the sum of the numbers on the inwardly directed edges equals that on the outwardly directed edges. Several classes of graphs, including K_n, for n ≥4, and K_{2n, 2m}, for n, m ≥ 2, are shown to be conservative. It is proven that the dual of a planar graceful graph is conservative, and that the converse of this result is false.     

Doubly stochastic matrices with prescribed positive spectrum

We show that for every set Λ={λ₁,λ₂,…,λ_n} of real numbers such that $\text{λ}{}_1\text{=1?λ}{}_2\text{???λ}{}_{\mathrm{n}}\text{\&\#62;0}$, there exists a doubly stochastic matrix with spectrum Λ. We present an explicit construction of such a matrix.     

On the number of positive solutions of elliptic systems

The paper deals with the existence, multiplicity and nonexistence of positive radial solutions for the elliptic system div(|?|^{p –2}?) + λk_i (|x |) fⁱ (u₁, …,u_n) = 0, p > 1, R₁ < |x | < R₂, u_i (x) = 0, on |x | = R₁ and R₂, i = 1, …, n, x ∈ ?^N , where k_i and fⁱ, i = 1, …, n, are continuous and nonnegative functions. Let u = (u₁, …, u_n), φ (t) = |t |^{p –2}t, fⁱ₀ = lim_{‖ u ‖→0}((fⁱ ( u ))/(φ (‖ u ‖))), fⁱ_∞= lim_{‖ u ‖→∞}((fⁱ ( u ))/(φ (‖ u ‖))), i = 1, …, n, f = (f¹, …, fⁿ), f ₀ = ∑ⁿ _{i =1} fⁱ ₀ and f _∞ = ∑ⁿ _{i =1} fⁱ _∞. We prove that either f ₀ = 0 and f _∞ = ∞ (superlinear), or f ₀ = ∞and f _∞ = 0 (sublinear), guarantee existence for all λ > 0. In addition, if fⁱ ( u ) > 0 for ‖ u ‖ > 0, i = 1, …, n, then either f ₀ = f _∞ = 0, or f ₀ = f _∞ = ∞, guarantee multiplicity for sufficiently large, or small λ, respectively. On the other hand, either f₀ and f_∞ > 0, or f₀ and f_∞ < ∞ imply nonexistence for sufficiently large, or small λ, respectively. Furthermore, all the results are valid for Dirichlet/Neumann boundary conditions. We shall use fixed point theorems in a cone. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

On Estrada index of trees

Let G be a graph on n vertices, and let λ₁,λ₂,…,λ_n be its eigenvalues. The Estrada index is defined as . We determine the unique tree with maximum Estrada index among the trees on n vertices with given matching number, and the unique tree with maximum Estrada index among the trees on n vertices with fixed diameter. For , we also determine the tree with maximum Estrada index among the trees on n vertices with maximum degree Δ. It gives a partial solution to the conjecture proposed by Ili? and Stevanovi? in Ref. [14].     

A degree bound on decomposable trees

A n-vertex graph is said to be decomposable if for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_i. In this paper, we focus on decomposable trees. We show that a decomposable tree has degree at most 4. Moreover, each degree-4 vertex of a decomposable tree is adjacent to a leaf. This leads to a polynomial time algorithm to decide if a multipode (a tree with only one vertex of degree greater than 2) is decomposable. We also exhibit two families of decomposable trees: arbitrary large trees with one vertex of degree 4, and trees with an arbitrary number of degree-3 vertices.     

Covering the vertices of a graph by cycles of prescribed length

The main theorem of that paper is the following: let G be a graph of order n, of size at least (n² - 3n + 6)/2. For any integers k, n₁, n₂,…,n_k such that n = n₁ + n₂ +. + n_k and n_i ? 3, there exists a covering of the vertices of G by disjoint cycles (C_i) =l…k with |C_i| = ni, except when n = 6, n₁ = 3, n₂ = 3, and G is isomorphic to G₁, the complement of G₁ consisting of a C₃ and a stable set of three vertices, or when n = 9, n₁ = n₂ = n₃ = 3, and G is isomorphic to G₂, the complement of G₂ consisting of a complete graph on four vertices and a stable set of five vertices. We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least n² - n + 2. For any integers s, n₁, n₂,…,n_s with n_i ? 2 and n = n₁ + n₂ + ? + n_s, there exists a covering of the vertices of G by s disjoint cycles C_i, with |C_i| = 2n_i.     

Packing graphs with odd and even trees

The Gyárfás-Lehel tree-packing conjecture asserts that any sequence T₁, T₂, …, T_n^?1 of trees with 1, 2, …, n - 1 edges packs into the complete graph K_n on n vertices. The present paper examines two conjectures that jointly imply the Gyárfás-Lehel conjecture: 1. For n even, any T₁, T₃, …, T_n^?1 pack into the half-complete graph Hn on n vertices.2. For n odd, any T₂, T₄, …, T_n^?1 pack into the half-complete graph Hn on n vertices. The H_n are uniquely defined by their degree sequences: H_n and H_n+1 are complements in K_n+1. It is shown that H_n and T_n+1 pack into H_n+2 if T_n+1 is a double star, unimodal triple star, interior-3 caterpillar, or scorpion. Hence Conjectures 1 and 2 are true for these specialized types of trees. The conjectures are also valid for all trees when n ≤ 9, so that the Gyárfás-Lehel conjecture holds for n ≤ 9.     

Continuum limits for classical sequential growth models

A random graph order, also known as a transitive percolation process, is defined by taking a random graph on the vertex set {0,…,n ? 1} and putting i below j if there is a path i = i₁…i_k = j in the graph with i₁ < … < i_k. Rideout and Sorkin 14 provide computational evidence that suitably normalized sequences of random graph orders have a “continuum limit.” We confirm that this is the case and show that the continuum limit is always a semiorder. Transitive percolation processes are a special case of a more general class called classical sequential growth models. We give a number of results describing the large‐scale structure of a general classical sequential growth model. We show that for any sufficiently large n, and any classical sequential growth model, there is a semiorder S on {0,…,n ‐ 1} such that the random partial order on {0,…,n ‐ 1} generated according to the model differs from S on an arbitrarily small proportion of pairs. We also show that, if any sequence of classical sequential growth models has a continuum limit, then this limit is (essentially) a semiorder. We give some examples of continuum limits that can occur. Classical sequential growth models were introduced as the only models satisfying certain properties making them suitable as discrete models for spacetime. Our results indicate that this class of models does not contain any that are good approximations to Minkowski space in any dimension ≥ 2. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010