On the rank spread of graphs

For a simple graph G?=?(𝒱, ?) with vertex-set 𝒱?=?{1,?…?,?n}, let 𝒮(G) be the set of all real symmetric n-by-n matrices whose graph is G. We present terminology linking established as well as new results related to the minimum rank problem, with spectral properties in graph theory. The minimum rank mr(G) of G is the smallest possible rank over all matrices in 𝒮(G). The rank spread r _v (G) of G at a vertex v, defined as mr(G)???mr(G???v), can take values ??∈?{0,?1,?2}. In general, distinct vertices in a graph may assume any of the three values. For ??=?0 or 1, there exist graphs with uniform r _v (G) (equal to the same integer at each vertex v). We show that only for ??=?0, will a single matrix A in 𝒮(G) determine when a graph has uniform rank spread. Moreover, a graph G, with vertices of rank spread zero or one only, is a λ-core graph for a λ-optimal matrix A in 𝒮(G). We also develop sufficient conditions for a vertex of rank spread zero or two and a necessary condition for a vertex of rank spread two.     

The spread of the unicyclic graphs

Let G be a simple connected graph with n vertices and n edges which we call a unicyclic graph. In this paper, we first investigate the least eigenvalue λ_n(G), then we present two sharp bounds on the spread s(G) of G.     

List Coloring of Random and Pseudo-Random Graphs

choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). It is shown that the choice number of the random graph G(n, p(n)) is almost surely whenever . A related result for pseudo-random graphs is proved as well. By a special case of this result, the choice number (as well as the chromatic number) of any graph on n vertices with minimum degree at least in which no two distinct vertices have more than common neighbors is at most . Received: October 13, 1997     

Size of nodal domains of the eigenvectors of a graph

Consider an eigenvector of the adjacency matrix of a G(n,p) graph. A nodal domain is a connected component of the set of vertices where this eigenvector has a constant sign. It is known that with high probability, there are exactly two nodal domains for each eigenvector corresponding to a nonleading eigenvalue. We prove that with high probability, the sizes of these nodal domains are approximately equal to each other.     

Some graft transformations and its application on a distance spectrum

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, we give some graft transformations that decrease and increase ?(G) and prove that the graph (obtained from the star S_n on n (n is not equal to 4, 5) vertices by adding an edge connecting two pendent vertices) has minimal distance spectral radius among unicyclic graphs on n vertices; while (obtained from a triangle K₃ by attaching pendent path P_n−3 to one of its vertices) has maximal distance spectral radius among unicyclic graphs on n vertices.     

The property of maximal eigenvectors of trees

Let T be a tree on n vertices and L(T) be its Laplacian matrix. The eigenvalues and eigenvectors of T are respectively referred to those of L(T). With respect to a given eigenvector Y of T, a vertex u of T is called a characteristic vertex if Y [u] = 0 and there is a vertex w adjacent to u with Y [w] ≠ 0; an edge e = (u, w) of G is called a characteristic edge if Y [u]Y [w] < 0. By 𝒞(T, Y) we denote the characteristic set of T with respect to the vector Y, which is defined as the collection of all characteristic vertices and characteristic edges of T corresponding to Y. Merris shows that 𝒞(T, Y) is fixed for all Fiedler vectors of the tree T. An eigenvector of T is called a k-vector (k ≥ 2) of T if this eigenvector corresponds to an eigenvalue λ _k with λ _k > λ _k?1, where λ₁, λ₂, …, λ _n are the eigenvalues of T arranged in non-decreasing order. A k-vector Y of T is called k-maximal if 𝒞(T, Y) has maximum cardinality among all k-vectors of T. We prove that (1) the characteristic set of T with respect to an arbitrary k-vector is contained in that with respect to any k-maximal vector; and consequently (2) the characteristic sets of T with respect to any two k-maximal vectors are same. Our result may be considered as a generalization of Merris' result as Fiedler vectors are 2-maximal.     

On integral sum graphs with a saturated vertex

As introduced by F.Harary in 1994, a graph G is said to be an integral sum graph if its vertices can be given a labeling f with distinct integers so that for any two distinct vertices u and v of G, uv is an edge of G if and only if f(u)+f(v) = f(w) for some vertex w in G.     

Intersection graphs of proper subtrees of unicyclic graphs

A graph is fraternally oriented iff for every three vertices u, ν, w the existence of the edges u → w and ν → w implies that u and ν are adjacent. A directed unicyclic graph is obtained from a unicyclic graph by orienting the unique cycle clockwise and by orienting the appended subtrees from the cycle outwardly. Two directed subtrees s, t of a directed unicyclic graph are proper if their union contains no (directed or undirected) cycle and either they are disjoint or one of them s has its root r(s) in t and contains all the successors of r(s) in t. In the present paper we prove that G is an intersection graph of a family of proper directed subtrees of a directed unicyclic graph iff it has a fraternal orientation such that for every vertex ν, G(Γⁱⁿν) is acyclic and G(Γ^outν) is the transitive closure of a tree. We describe efficient algorithms for recognizing when such graphs are perfect and for testing isomorphism of proper circular-arc graphs.     

Local and global average degree in graphs and multigraphs

A vertex v of a graph G is called groupie if the average degree t_v of all neighbors of v in G is not smaller than the average degree t_G of G. Every graph contains a groupie vertex; the problem of whether or not every simple graph on ≧2 vertices has at least two groupie vertices turned out to be surprisingly difficult. We present various sufficient conditions for a simple graph to contain at least two groupie vertices. Further, we investigate the function f(n) = max min_v (t_v/t_G), where the maximum ranges over all simple graphs on n vertices, and prove that f(n) = 1/42n + o(1). The corresponding result for multigraphs is in sharp contrast with the above. We also characterize trees in which the local average degree t_v is constant.     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

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.     

A short and unified proof of Yu et al.?s two results on the eccentric distance sum

The eccentric distance sum (EDS) is a novel topological index that offers a vast potential for structure activity/property relationships. For a connected graph G, the eccentric distance sum is defined as ξd(G)=_∑v∈V(G)ecG(v)DG(v), where ecG(v) is the eccentricity of a vertex v in G and DG(v) is the sum of distances of all vertices in G from v. More recently, Yu et al. [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 99-107] proved that for an n-vertex tree T, ξd(T)?4n²−9n+5, with equality holding if and only if T is the n-vertex star Sn, and for an n-vertex unicyclic graph G, ξd(G)?4n²−9n+1, with equality holding if and only if G is the graph obtained by adding an edge between two pendent vertices of n-vertex star. In this note, we give a short and unified proof of the above two results.     

On bounds for the cutting number of a graph

The cutting number of a vertex v of a finite graph G = (V,E) is a natural measure of the extent to which the removal of v disconnects the graph. Precisely, the cutting number c(v) of v is defined as the number of pairs of vertices {u,w} of G such that u,w ≠ v and every u-w path contains v. The cutting number c(G) of G is the maximum value of c(v) over all vertices in V. We provide exact bounds on the cutting number of G in terms of order and diameter of the graph.     

On minimum metric dimension of honeycomb networks

A minimum metric basis is a minimum set W of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex wW with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. The honeycomb and hexagonal networks are popular mesh-derived parallel architectures. Using the duality of these networks we determine minimum metric bases for hexagonal and honeycomb networks.     

Connected Resolvability of Graphs

For an ordered set W = {w ₁, w ₂,..., w _k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w ₁), d(v, w ₂),... d(v, w _k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n?1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n?1 if and only if G = K _n or G = K _1,n?1. It is also shown that for positive integers a, b with a ≤ b, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if $\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$ Several other realization results are present. The connected resolving numbers of the Cartesian products G × K ₂ for connected graphs G are studied.     

Degree Distance of Unicyclic Graphs with Given Matching Number

Let G be a connected graph with vertex set V(G). The degree distance of G is defined as ${D'(G) = \sum_{\{u, v\}\subseteq V(G)} (d_G(u) + d_G (v))\, d(u,v)}$ , where d _G (u) is the degree of vertex u, d(u, v) denotes the distance between u and v, and the summation goes over all pairs of vertices in G. In this paper, we characterize n-vertex unicyclic graphs with given matching number and minimal degree distance.     

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.     

On the nullity and the matching number of unicyclic graphs

Let G be a graph with n vertices and ν(G) be the matching number of G. Let η(G) denote the nullity of G (the multiplicity of the eigenvalue zero of G). It is well known that if G is a tree, then η(G)=n-2ν(G). Tan and Liu [X. Tan, B. Liu, On the nullity of unicyclic graphs, Linear Alg. Appl. 408 (2005) 212-220] proved that the nullity set of all unicyclic graphs with n vertices is {0,1,…,n-4} and characterized the unicyclic graphs with η(G)=n-4. In this paper, we characterize the unicyclic graphs with η(G)=n-5, and we prove that if G is a unicyclic graph, then η(G) equals , or n-2ν(G)+2. We also give a characterization of these three types of graphs. Furthermore, we determine the unicyclic graphs G with η(G)=0, which answers affirmatively an open problem by Tan and Liu.     

Relative length of long paths and cycles in graphs with large degree sums

For a graph G, p(G) denotes the order of a longest path in G and c(G) the order of a longest cycle. We show that if G is a connected graph n ≥ 3 vertices such that d(u) + d(v) + d(w) ≧ n for all triples u, v, w of independent vertices, then G satisfies c(G) ≥ p(G) – 1, or G is in one of six families of exceptional graphs. This generalizes results of Bondy and of Bauer, Morgana, Schmeichel, and Veldman. © 1995, John Wiley & Sons, Inc.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.