Solving linear programs from sign patterns

This paper is an attempt to provide a connection between qualitative matrix theory and linear programming. A linear program is said to be sign-solvable if the set of sign patterns of the optimal solutions is uniquely determined by the sign patterns of A, b, and c. It turns out to be NP-hard to decide whether a given linear program is sign-solvable or not. We then introduce a class of sign-solvable linear programs in terms of totally sign-nonsingular matrices, which can be recognized in polynomial time. For a linear program in this class, we devise an efficient combinatorial algorithm to obtain the sign pattern of an optimal solution from the sign patterns of A, b, and c. The algorithm runs in O(mγ) time, where m is the number of rows of A and γ is the number of all nonzero entries in A, b, and c.     

Primitive digraphs with the largest scrambling index

The scrambling index of a primitive digraph D is the smallest positive integer k such that for every pair of vertices u and v, there is a vertex w such that we can get to w from u and v in D by directed walks of length k; it is denoted by k(D). In [M. Akelbek, S. Kirkland, Coefficients of ergodicity and the scrambling index, preprint] we gave the upper bound on k(D) in terms of the order and the girth of a primitive digraph D. In this paper, we characterize all the primitive digraphs such that the scrambling index is equal to the upper bound.     

Generalized competition index of a primitive digraph

For positive integers k and m, and a digraph D, the k-step m-competition graph of D has the same set of vertices as D and an edge between vertices x and y if and only if there are distinct m vertices v₁,v₂,…,v_m in D such that there are directed walks of length k from x to v_i and from y to v_i for 1?i?m. In this paper, we present the definition of m-competition index for a primitive digraph. The m-competition index of a primitive digraph D is the smallest positive integer k such that is a complete graph. We study m-competition indices of primitive digraphs and provide an upper bound for the m-competition index of a primitive digraph.     

A bound on the generalized competition index of a primitive matrix using Boolean rank

For a positive integer m where 1?m?n, the m-competition index (generalized competition index) of a primitive digraph is the smallest positive integer k such that for every pair of vertices x and y, there exist m distinct vertices v₁,v₂,…,v_m such that there are directed walks of length k from x to v_i and from y to v_i for 1?i?m. The m-competition index is a generalization of the scrambling index and the exponent of a primitive digraph. In this study, we determine an upper bound on the m-competition index of a primitive digraph using Boolean rank and give examples of primitive Boolean matrices that attain the bound.     

The scrambling index of symmetric primitive matrices

A nonnegative square matrix A is primitive if some power A^k>0 (that is, A^k is entrywise positive). The least such k is called the exponent of A. In [2], Akelbek and Kirkland defined the scrambling index of a primitive matrix A, which is the smallest positive integer k such that any two rows of A^k have at least one positive element in a coincident position. In this paper, we give a relation between the scrambling index and the exponent for symmetric primitive matrices, and determine the scrambling index set for the class of symmetric primitive matrices. We also characterize completely the symmetric primitive matrices in this class such that the scrambling index is equal to the maximum value.     

Potentially nilpotent and spectrally arbitrary even cycle sign patterns

An n × n sign pattern S_n is potentially nilpotent if there is a real matrix having sign pattern S_n and characteristic polynomial xⁿ. A new family of sign patterns C_n with a cycle of every even length is introduced and shown to be potentially nilpotent by explicitly determining the entries of a nilpotent matrix with sign pattern C_n. These nilpotent matrices are used together with a Jacobian argument to show that C_n is spectrally arbitrary, i.e., there is a real matrix having sign pattern C_n and characteristic polynomial for any real μ_i. Some results and a conjecture on minimality of these spectrally arbitrary sign patterns are given.     

On tricyclic graphs of a given diameter with minimal energy

The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. Let G(n,d) be the class of tricyclic graphs G on n vertices with diameter d and containing no vertex disjoint odd cycles C_p,C_q of lengths p and q with p+q≡2(mod4). In this paper, we characterize the graphs with minimal energy in G(n,d).     

The smallest signless Laplacian spectral radius of graphs with a given clique number

The signless Laplacian spectral radius of a graph G is the largest eigenvalue of its signless Laplacian matrix. In this paper, the first four smallest values of the signless Laplacian spectral radius among all connected graphs with maximum clique of size greater than or equal to 2 are obtained.     

Spectral radius of digraphs with given dichromatic number

Let D be a digraph with vertex set V(D). A partition of V(D) into k acyclic sets is called a k-coloring of D. The minimum integer k for which there exists a k-coloring of D is the dichromatic number χ(D) of the digraph D. Denote G_n,k the set of the digraphs of order n with the dichromatic number k≥2. In this note, we characterize the digraph which has the maximal spectral radius in G_n,k. Our result generalizes the result of [8] by Feng et al.     

The forcing number of graphs with given girth

In this paper, we study a dynamic coloring of the vertices of a graph G that starts with an initial subset S of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set S is called a forcing set of G if, by iteratively applying the forcing process, every vertex in G becomes colored. The forcing number, originally known as the zero forcing number, and denoted F (G), of G is the cardinality of a smallest forcing set of G. We study lower bounds on the forcing number in terms of its minimum degree and girth, where the girth g of a graph is the length of a shortest cycle in the graph. Let G be a graph with minimum degree δ ≥ 2 and girth g ≥ 3. Davila and Kenter [Theory and Applications of Graphs, Volume 2, Issue 2, Article 1, 2015] conjecture that F (G) ≥ δ + (δ ? 2)(g ? 3). This conjecture has recently been proven for g ≤ 6. The conjecture is also proven when the girth g ≥ 7 and the minimum degree is sufficiently large. In particular, it holds when g = 7 and δ ≥ 481, when g = 8 and δ ≥ 649, when g = 9 and δ ≥ 30, and when g = 10 and δ ≥ 34. In this paper, we prove the conjecture for g ∈ {7, 8, 9, 10} and for all values of δ ≥ 2.     

Spectral radius of graphs with given matching number

In this paper, we show that of all graphs of order n with matching number β, the graphs with maximal spectral radius are K_n if n = 2β or 2β + 1; if 2β + 2 ? n < 3β + 2; or if n = 3β + 2; if n > 3β + 2, where is the empty graph on t vertices.     

On the spectral radius of bipartite graphs with given diameter

Let GB(n,d) be the set of bipartite graphs with order n and diameter d. This paper characterizes the extremal graph with the maximal spectral radius in GB(n,d). Furthermore, the maximal spectral radius is a decreasing function on d. At last, bipartite graphs with the second largest spectral radius are determined.     

Coefficients of ergodicity and the scrambling index

For a primitive stochastic matrix S, upper bounds on the second largest modulus of an eigenvalue of S are very important, because they determine the asymptotic rate of convergence of the sequence of powers of the corresponding matrix. In this paper, we introduce the definition of the scrambling index for a primitive digraph. The scrambling index of a primitive digraph D is the smallest positive integer k such that for every pair of vertices u and v, there is a vertex w such that we can get to w from u and v in D by directed walks of length k; it is denoted by k(D). We investigate the scrambling index for primitive digraphs, and give an upper bound on the scrambling index of a primitive digraph in terms of the order and the girth of the digraph. By doing so we provide an attainable upper bound on the second largest modulus of eigenvalues of a primitive matrix that make use of the scrambling index.     

The Laplacian spectral radius for unicyclic graphs with given independence number

In this paper, we give a complete characterization of the extremal graphs with maximal Laplacian spectral radius among all unicyclic graphs with given order and given number of pendent vertices. Then we study the Laplacian spectral radius of unicyclic graphs with given independence number and characterize the extremal graphs completely.     

Connected graphs containing a given connected graph as a unique greatest common subgraph

Those connected graphsG are determined for which there exist nonisomorphic connected graphs of equal size containingG as a unique greatest common subgraph. Analogous results are also obtained for weakly connected and strongly connected digraphs, as well as for induced subgraphs and induced subdigraphs.This research was supported by a Western Michigan University faculty research fellowship.This research was supported in part by a Western Michigan University research assistantship from the Graduate College and the College of Arts and Sciences.     

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

Clique partitions of distance multigraphs

We consider the minimum number of cliques needed to partition the edge set of D(G), the distance multigraph of a simple graph G. Equivalently, we seek to minimize the number of elements needed to label the vertices of a simple graph G by sets so that the distance between two vertices equals the cardinality of the intersection of their labels. We use a fractional analogue of this parameter to find lower bounds for the distance multigraphs of various classes of graphs. Some of the bounds are shown to be exact.