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.     

Strong subtournaments containing a given vertex in regular multipartite tournaments

If x is a vertex of a digraph D, then we denote by d⁺(x) and d⁻(x) the outdegree and the indegree of x, respectively. The global irregularity of a digraph D is defined by

     

Characterization of projective graphs

We denote the distance between vertices x and y of a graph by d(x, y), and p_ij(x, y) = ∥ {z : d(x, z) = i, d(y, z) = j} ∥. The (s, q, d)-projective graph is the graph having the s-dimensional subspaces of a d-dimensional vector space over GF(q) as vertex set, and two vertices x, y adjacent iff $\text{dim}\text{(x ? y) = s ? 1}$. These graphs are regular graphs. Also, there exist integers λ and μ > 4 so that μ is a perfect square, p₁₁(x, y) = λ whenever d(x, y) = 1, and p₁₁(x, y) = μ whenever d(x, y) = 2. The (s, q, d)-projective graphs where $\text{2d}\text{3}\text{≤ s < d ? 2}$ and $\text{(s, q, d) ≠ (}\text{2d}\text{3}\text{, 2, d)}$, are characterized by the above conditions together with the property that there exists an integer r satisfying certain inequalities.     

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

On the eccentric distance sum of trees and unicyclic graphs

Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=_∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum.     

Integro-local theorems for sums of independent random vectors in the series scheme

Let S(n) = ξ(1)+?+ξ(n) be a sum of independent random vectors ξ(i) = ξ _(n)(i) with general distribution depending on a parameter n. We find sufficient conditions for the uniform version of the integro-local Stone theorem to hold for the asymptotics of the probability P(S(n) ∈ Δ[x), where Δ[x) is a cube with edge Δ and vertex at a point x.     

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.     

A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees

Let G be a connected simple graph, let X?V (^G) and let f be a mapping from X to the set of integers. When X is an independent set, Frank and Gyárfás, and independently, Kaneko and Yoshimoto gave a necessary and sufficient condition for the existence of spanning tree T in G such that d _T (x) for all x ∈ X, where d _T (x) is the degree of x and T. In this paper, we extend this result to the case where the subgraph induced by X has no induced path of order four, and prove that there exists a spanning tree T in G such that d _T (x) ≥ f(x) for all x ∈ X if and only if for any nonempty subset S ? X, |N _G (S) ? S| ? f(S) + 2|S| ? ω _G (S) ≥, where ω _G (S) is the number of components of the subgraph induced by S.     

Graphs with small diameter determined by their <Emphasis Type="Italic">D</Emphasis>-spectra

Let G be a connected graph with vertex set V(G) = {v₁, v₂,..., v _n }. The distance matrix D(G) = (d _ij )_n×n is the matrix indexed by the vertices of G, where d _ij denotes the distance between the vertices v _i and v _j . Suppose that λ₁(D) ≥ λ₂(D) ≥... ≥ λ _n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.     

Domains with growth conditions for the quasihyperbolic metric

For a given growth functionH, we say that a domainD ?R ⁿ is anH-domain if δ_D x≤δ_D(x ₀)H(k _D(x,x ₀)),x ∈D, where δ_D(x)=d(x?D) andk _D denotes the quasihyperbolic distance. We show that ifH satisfiesH(0)=1, |H'|≤H, andH"≤H, then there exists an extremalH-domain. Using this fact, we investigate some fundamental properties ofH-domains.     

Equilibrium resource distribution in a network model

A network is modeled by a weighted undirected graph G. Some certain time invariable resource is assigned to each node and is distributed among the incident edges at each time (time is assumed to be discrete). A state of the network corresponds to a distribution of resources of all nodes among the edges of G. At each time a vertex i evaluates its relationship with an adjacent vertex j according to a given function c _ij (x _ij , x _ji ) of the resources x _ij and x _ji provided by the nodes i and j to the edge (i, j). Since resources of the nodes are redistributed at every time, the state of the system varies in time. Some sufficient conditions are found for the existence of the limit and equilibrium states of the model; and precise formulas are given to compute these states in the case of a special function c _ij for an arbitrary graph G.     

Hamilton cycles,avoiding prescribed arcs,in close-to-regular tournaments

The local irregularity of a digraph D is defined as i_l(D) = max {|d⁺ (x) − d⁻ (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V₁, V₂, …, V_c} be a partition of V(T) such that |V₁| ≥ |V₂| ≥ … ≥ |V_c|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if |V(T)| ≥ max{2i_l(T) + 2|V₁| + 2|V₂| − 2, i_l(T) + 3|V₁| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., i_l(T) = 0), then we state slightly better lower bounds for |V(T)| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999     

Lipschitz equivalence of fractal sets in ?

Let T(q,D) be a self-similar (fractal) set generated by $ \left\{ {fi(x) = \frac{1} {q}(x + d_i )} \right\}_{i = 1}^N $ where integer q > 1 and D = {d ₁, d ₂, ??, d _N } ? ?. To show the Lipschitz equivalence of T(q,D) and a dust-like T(q,C), one general restriction is D ? ? by Peres et al. [Israel J Math, 2000, 117: 353?C379]. In this paper, we obtain several sufficient criterions for the Lipschitz equivalence of two self-similar sets by using dust-like graph-directed iterating function systems and combinatorial techniques. Several examples are given to illustrate our theory.     

Numerical solutions with a priori error bounds for coupled self-adjoint time dependent partial differential systems

This paper is concerned with the construction of accurate continuous numerical solutions for partial self-adjoint differential systems of the type (P(t) u_t)_t = Q(t)u_xx, u(0, t) = u(d, t) = 0, u(x, 0) = f(x), u_t(x, 0) = g(x), 0 ≤ x ≤ d, t >- 0, where P(t), Q(t) are positive definite oR^r×r-valued functions such that P′(t) and Q′(t) are simultaneously semidefinite (positive or negative) for all t ≥ 0. First, an exact theoretical series solution of the problem is obtained using a separation of variables technique. After appropriate truncation strategy and the numerical solution of certain matrix differential initial value problems the following question is addressed. Given T > 0 and an admissible error ϵ > 0 how to construct a continuous numerical solution whose error with respect to the exact series solution is smaller than ϵ, uniformly in D(T) = {(x, t); 0 ≤ x ≤ d, 0 ≤ t ≤ T}. Uniqueness of solutions is also studied.     

The Terwilliger algebra of a distance-regular graph of negative type

Let Γ denote a distance-regular graph with diameter D?3. Assume Γ has classical parameters (D,b,α,β) with b<-1. Let X denote the vertex set of Γ and let A∈Mat_X(C) denote the adjacency matrix of Γ. Fix x∈X and let A^∗∈Mat_X(C) denote the corresponding dual adjacency matrix. Let T denote the subalgebra of Mat_X(C) generated by A,A^∗. We call T the Terwilliger algebra of Γ with respect to x. We show that up to isomorphism there exist exactly two irreducible T-modules with endpoint 1; their dimensions are D and 2D-2. For these T-modules we display a basis consisting of eigenvectors for A^∗, and for each basis we give the action of A.     

Trees of extremal connectivity index

The connectivity index w_α(G) of a graph G is the sum of the weights (d(u)d(v))^α of all edges uv of G, where α is a real number (α≠0), and d(u) denotes the degree of the vertex u. Let T be a tree with n vertices and k pendant vertices. In this paper, we give sharp lower and upper bounds for w₁(T). Also, for -1?α<0, we give a sharp lower bound and a upper bound for w_α(T).     

Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph

Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex v_i by d(v_i). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v₁),d(v₂),…,d(v_n)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q₁(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G and give a new proving method on another sharp upper bound for q₁(G). Then we present three sharp lower bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G. Moreover, we determine all extremal graphs which attain these sharp bounds.     

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     

Nonlinear equations involving m-accretive operators

Let X be a Banach space and T an m-accretive operator defined on a subset D(T) of X and taking values in 2^x. For the class of spaces whose bounded closed and convex subsets have the fixed point property for nonexpansive self-mappings, it is shown here that two boundary conditions which imply existence of zeroes for T, appear to be equivalent. This fact is then used to prove that if there exists x₀?D(T) and a bounded open neighborhood U of x₀, such that $\text{¦T(x}{}_0\text{)¦ < r ? ¦T(x)¦}$ for all x??U ∩ D(T), then the open ball B(0; r) is contained in the range of T.     

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998