Rank numbers of grid graphs

A ranking of a graph is a labeling of the vertices with positive integers such that any path between vertices of the same label contains a vertex of greater label. The rank number of a graph is the smallest possible number of labels in a ranking. We find rank numbers of the Möbius ladder, K_s×P_n, and P₃×P_n. We also find bounds for rank numbers of general grid graphs P_m×P_n.     

Graphs with full rank 3-color matrix and few 3-colorings

We exhibit a counterexample to a conjecture of Thomassen stating that the number of distinct 3-colorings of every graph whose 3-color matrix has full column rank is superpolynomial in the number of vertices.     

Maximum order of trees and bipartite graphs with a given rank

The rank of a graph is that of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced trees as well as bipartite graphs with a given rank and characterize those graphs achieving the maximum order.     

Maximum Order of Triangle‐Free Graphs with a Given Rank

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced triangle‐free graphs with a given rank and characterize all such graphs achieving the maximum order.     

Zero forcing parameters and minimum rank problems

The zero forcing number Z(G), which is the minimum number of vertices in a zero forcing set of a graph G, is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by G. It is shown that for a connected graph of order at least two, no vertex is in every zero forcing set. The positive semidefinite zero forcing number Z₊(G) is introduced, and shown to be equal to |G|-OS(G), where OS(G) is the recently defined ordered set number that is a lower bound for minimum positive semidefinite rank. The positive semidefinite zero forcing number is applied to the computation of positive semidefinite minimum rank of certain graphs. An example of a graph for which the real positive symmetric semidefinite minimum rank is greater than the complex Hermitian positive semidefinite minimum rank is presented.     

The minimum semidefinite rank of a triangle-free graph

We employ a result of Moshe Rosenfeld to show that the minimum semidefinite rank of a triangle-free graph with no isolated vertex must be at least half the number of its vertices. We define a Rosenfeld graph to be such a graph that achieves equality in this bound, and we explore the structure of these special graphs. Their structure turns out to be intimately connected with the zero-nonzero patterns of the unitary matrices. Finally, we suggest an exploration of the connection between the girth of a graph and its minimum semidefinite rank, and provide a conjecture in this direction.     

Linearly independent vertices and minimum semidefinite rank

We study the minimum semidefinite rank of a graph using vector representations of the graph and of certain subgraphs. We present a sufficient condition for when the vectors corresponding to a set of vertices of a graph must be linearly independent in any vector representation of that graph, and conjecture that the resulting graph invariant is equal to minimum semidefinite rank. Rotation of vector representations by a unitary matrix allows us to find the minimum semidefinite rank of the join of two graphs. We also improve upon previous results concerning the effect on minimum semidefinite rank of the removal of a vertex.     

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.     

Rank, term rank, and chromatic number

Let G be a graph with a nonempty edge set, and with rank rk(G), term rank Rk(G), and chromatic number χ(G). We characterize Rk(G) as being the maximum number of colors in certain proper colorings of G. In particular, we observe that χ(G)Rk(G), with equality holding if and only if (besides isolated vertices) G is either complete or a star. For a twin-free graph G, we observe the bound and we show that this bound is sharp.     

Quasi-randomness and the distribution of copies of a fixed graph

We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices.     

Reverse mathematics and rank functions for directed graphs

A rank function for a directed graph G assigns elements of a well ordering to the vertices of G in a fashion that preserves the order induced by the edges. While topological sortings require a one-to-one matching of vertices and elements of the ordering, rank functions frequently must assign several vertices the same value. Theorems stating basic properties of rank functions vary significantly in logical strength. Using the techniques of reverse mathematics, we present results that require the subsystems , , , and . Received: 29 December 1998     

On WL-rank of Deza Cayley graphs

The WL-rank of a graph Γ is defined to be the rank of the coherent configuration of Γ. We construct a new infinite family of strictly Deza Cayley graphs for which the WL-rank is equal to the number of vertices. The graphs from this family are divisible design and integral.     

Rank three permutation groups with rank three subconstituents

Finite permutation groups of rank 3 such that both the subconstituents have rank 3 are classified. This is equivalent to classifying all finite undirected graphs with the following property: every isomorphism between subgraphs on at most three vertices is a restriction of an automorphism of the graph.     

On Minimum Edge Ranking Spanning Trees

In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard. Furthermore, we present an approximation algorithm for MERST, which realizes its worst case performance ratio where n is the number of vertices in G and Δ* is the maximum degree of a spanning tree whose maximum degree is minimum. Although the approximation algorithm is a combination of two existing algorithms for the restricted spanning tree problem and for the minimum edge ranking problem of trees, the analysis is based on novel properties of the edge ranking of trees.     

A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs

The metric dimension dim(G)of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices.The zero forcing number Z(G)of a graph G is the minimum cardinality of a set S of black vertices(whereas vertices in V(G)\S are colored white)such that V(G)is turned black after finitely many applications of"the color-change rule":a white vertex is converted black if it is the only white neighbor of a black vertex.We show that dim(T)≤Z(T)for a tree T,and that dim(G)≤Z(G)+1 if G is a unicyclic graph;along the way,we characterize trees T attaining dim(T)=Z(T).For a general graph G,we introduce the"cycle rank conjecture".We conclude with a proof of dim(T)-2≤dim(T+e)≤dim(T)+1 for e∈E(T).     

An algorithm for the determination of longest distances in a graph

This paper presents an algorithm for ranking the vertices of a directed graph. Its space and time requirements are bounded byc ₁ n ² +c ₂, wheren is the number of vertices of the graph andc ₁,c ₂ are positive constants which are independent of the size or other properties of the graph.The algorithm can be easily modified to solve the problem of determining longest distances from a vertex to all other vertices in a positive real valued graph with at mostc ₁ n ² +c ₂ elementary operations; the same result holds for shortest distances in negative real valued graphs.     

A Characterization of Cubic Graphs with Paired-Domination Number Three-Fifths Their Order

A paired-dominating set of a graph is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph. Recently, Chen et al. (Acta Math Sci Ser A Chin Ed 27(1):166–170, 2007) proved that a cubic graph has paired-domination number at most three-fifths the number of vertices in the graph. In this paper, we show that the Petersen graph is the only connected cubic graph with paired-domination number three-fifths its order.     

Classes of graphs with minimum skew rank 4

The minimum skew rank of a simple graph G   is the smallest possible rank among all real skew-symmetric matrices whose (i,j)$(i,j)$-entry is nonzero if and only if the edge joining i and j is in G. It is known that a graph has minimum skew rank 2 if and only if it consists of a complete multipartite graph and some isolated vertices. Some necessary conditions for a graph to have minimum skew rank 4 are established, and several families of graphs with minimum skew rank 4 are given. Linear algebraic techniques are developed to show that complements of trees and certain outerplanar graphs have minimum skew rank 4.     

Maximal independent sets on a grid graph

An independent vertex set of a graph is a set of vertices of the graph in which no two vertices are adjacent, and a maximal independent set is one that is not a proper subset of any other independent set. In this paper we count the number of maximal independent sets of vertices on a complete rectangular grid graph. More precisely, we provide a recursive matrix-relation producing the partition function with respect to the number of vertices. The asymptotic behavior of the maximal hard square entropy constant is also provided. We adapt the state matrix recursion algorithm, recently invented by the author to answer various two-dimensional regular lattice model problems in enumerative combinatorics and statistical mechanics.     

Exotic n-universal graphs

An n-universal graph is a graph that contains as an induced subgraph a copy of every graph on n vertices. It is shown that for each positive integer n > 1 there exists an n-universal graph G on 4ⁿ - 1 vertices such that G is a (v, k, λ)-graph, and both G and its complement G¯ are 1-transitive in the sense of W. T. Tutte and are of diameter 2. The automorphism group of G is a transitive rank 3 permutation group, i.e., it acts transitively on (1) the vertices of G, (2) the ordered pairs uv of adjacent vertices of G, and (3) the ordered pairs xy of nonadjacent vertices of G.