Search

It is known that there are precisely three transitive permutation groups of degree $6$ that admit an invariant partition with three parts of size $2$ such that the kernel of the action on the parts has order $4$; these groups are called $A_4(6)$, $S_4(6d)$ and $S_4(6c)$. For each $L\in \{A_4(6), S_4(6d), S_4(6c)\}$, we construct an infinite family of finite connected $6$-valent graphs $\{\Gamma_n\}_{n\in \mathbb{N}}$ and arc-transitive groups $G_n \le \rm{Aut}(\Gamma_n)$ such that the permutation group induced by the action of the vertex-stabiliser $(G_n)_v$ on the neighbourhood of a vertex $v$ is permutation isomorphic to $L$, and such that $|(G_n)_v|$ is exponential in $|\rm{V}(\Gamma_n)|$. These three groups were the only transitive permutation groups of degree at most $7$ for which the existence of such a family was undecided. In the process, we construct an infinite family of cubic $2$-arc-transitive graphs such that the dimension of the $1$-eigenspace over the field of order $2$ of the adjacency matrix of the graph grows linearly with the order of the graph.

We derive a correspondence between the eigenvalues of the adjacency matrix $A$ and the signless Laplacian matrix $Q$ of a graph $G$ when $G$ is $(d_1,d_2)$-biregular by using the relation $A^2=(Q-d_1I)(Q-d_2I)$. This motivates asking when it is possible to have $X^r=f(Y)$ for $f$ a polynomial, $r>0$, and $X,\ Y$ matrices associated to a graph $G$. It turns out that, essentially, this can only happen if $G$ is either regular or biregular.

Given a digraph G, we propose a new method to find the recurrence equation for the number of vertices n_k of the k-iterated line digraph L_k(G), for k>= 0, where L_0(G) = G. We obtain this result by using the minimal polynomial of a quotient digraph pi(G) of G. We show some examples of this method applied to the so-called cyclic Kautz, the unicyclic, and the acyclic digraphs. In the first case, our method gives the enumeration of the ternary length-2 squarefree words of any length.

The article gives a thorough introduction to spectra of digraphs via its Hermitian adjacency matrix. This matrix is indexed by the vertices of the digraph, and the entry corresponding to an arc from x to y is equal to the complex unity i (and its symmetric entry is −i) if the reverse arc yx is not present. We also allow arcs in both directions and unoriented edges, in which case we use 1 as the entry. This allows to use the definition also for mixed graphs. This matrix has many nice properties; it has real eigenvalues and the interlacing theorem holds for a digraph and its induced subdigraphs. Besides covering the basic properties, we discuss many differences from the properties of eigenvalues of undirected graphs and develop basic theory. The main novel results include the following. Several surprising facts are discovered about the spectral radius; some consequences of the interlacing property are obtained; operations that preserve the spectrum are discussed—they give rise to a large number of cospectral digraphs; for every 0≤α≤3, all digraphs whose spectrum is contained in the interval (−α,α) are determined.

Let λ2G and i¾?G denote the second largest eigenvalue and the maximum number of edge-disjoint spanning trees of a graph G, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and bounds of i¾?G, Cioaba and Wong conjectured that for any integers d,ki¾?2 and a d-regular graph G, if λ2G

In this article, we study problems where one has to prove that certain graph parameter attains its maximum at the star and its minimum at the path among the trees on a fixed number of vertices. We give many applications of the so-called generalized tree shift which seems to be a powerful tool to attack the problems of the above-mentioned kind. We show that the generalized tree shift increases the largest eigenvalue of the adjacency matrix and Laplacian matrix, decreases the coefficients of the characteristic polynomials of these matrices in absolute value. We will prove similar theorems for the independence polynomial and the edge cover polynomial. The generalized tree shift induces a partially ordered set on trees having fixed number of vertices. The smallest element of this poset is the path, largest element is the star. Hence, the above-mentioned results imply the extremality of the path and the star for these parameters.

A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. Recently, Csikvari proved the existence of integral trees of any even diameter. In the odd case, integral trees have been constructed with diameter at most 7. In this article, we show that for every odd integer n>1, there are infinitely many integral trees of diameter n. © 2011 Wiley Periodicals, Inc. J Graph Theory, © 2012 Wiley Periodicals, Inc. (Contract grant sponsor: IPM (to E. G. and A. M.).)

We consider extremal problems for algebraic graphs, that is, graphs whose vertices correspond to vectors in ℝd, where two vectors are connected by an edge according to an algebraic condition. We also derive a lower bound on the rank of the adjacency matrix of a general abstract graph using the number of 4-cycles and a parameter which measures how close the graph is to being regular. From this, we derive a rank bound for the adjacency matrix A of any simple graph with n vertices and E edges which does not contain a copy of **image**. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:91-102, 2011 (This research has been conducted while H. Tracy Hall was visiting the Technion—Israeli Institute of Technology.)

We show that the number of points with pairwise different sets of neighbors in a graph is O(2r/2), where r is the rank of the adjacency matrix. We also give an example that achieves this bound. © 1996 John Wiley & Sons, Inc.

A generalized Steinhaus graph of order n and type s is a graph with n vertices whose adjacency matrix (ai,j) satisfies the relation where 2 ≦i≦n−1, i + s(i − 1 ≦ j ≦ n, cr,i,j ϵ {0,1} for all 0 ≦ r ≦ s(i) −1 and cs(i)−1,i,j = 1. The values of s(i) and cr,i,j are fixed but arbitrary. Generalized Steinhaus graphs in which each edge has probability ½ are considered. In an article by A. Blass and F. Harary [“Properties of Almost All Graphs and Complexes,” Journal of Graph Theory, Vol. 3 (1976), pp. 225–240], a collection of first-order axioms are given from which any first-order property in graph theory or its negation can be deduced. We show that almost all generalized Steinhaus graphs satisfy these axioms. Thus the first-order theory of random generalized Steinhaus graphs is identical with the theory of random graphs. Quasi-random properties of graphs are described by F. R. K. Chung, R. L. Graham, and R. M. Wilson, [“Quasi-Random Graphs,” Combinatorica, Vol. 9 (1989), pp. 345–362]. We conclude by demonstrating that almost all generalized Steinhaus graphs obey Property 2 and hence all equivalent quasi-random properties. © 1996 John Wiley & Sons, Inc.

It is well known that the smallest eigenvalue of the adjacency matrix of a connected d-regular graph is at least − d and is strictly greater than − d if the graph is not bipartite. More generally, for any connected graph G = (V, E), consider the matrix Q = D + A where D is the diagonal matrix of degrees in the graph G and A is the adjacency matrix of G. Then Q is positive semidefinite, and the smallest eigenvalue of Q is 0 if and only if G is bipartite. We will study the separation of this eigenvalue from 0 in terms of the following measure of nonbipartiteness of G. For any S ⊆ V, we denote by emin(S) the minimum number of edges that need to be removed from the induced subgraph on S to make it bipartite. Also, we denote by cut(S) the set of edges with one end in S and the other in V − S. We define the parameter Ψ as ***image*** The parameter Ψ is a measure of the nonbipartiteness of the graph G. We will show that the smallest eigenvalue of Q is bounded above and below by functions of Ψ. For d-regular graphs, this characterizes the separation of the smallest eigenvalue of the adjacency matrix from −d. These results can be easily extended to weighted graphs. © 1994 Wiley Periodicals, Inc.

Jo Heath and the author found a set of necessary and sufficient conditions for the existence of an exactly k-to-1 map from a graph G to a graph H. These conditions were all local ones. Here this result is used to give necessary and sufficient conditions for the existence of an exactly k-to-1 map from G to H when k is sufficiently large. The conditions for this are global in nature. © 1993 John Wiley & Sons, Inc.

Let χ be an irreducible character of the symmetric group Sn. For an n-by-n matrix A = (aij), define If G is a graph, let D(G) be the diagonal matrix of its vertex degrees and A(G) its adjacency matrix. Let y and z be independent indeterminates, and define L(G) = yD(G) + zA(G). Suppose tn is the number of trees on n vertices and sn is the number of such trees T for which there exists a nonisomorphic tree T such that dχ(xl - L(T)) = dx(xl - L(T)) for every irreducible character χ of Sn. Then limn∞Sn/tn = 1. © 1993 John Wiley & Sons, Inc.

A Steinhaus graph is a graph with n vertices whose adjacency matrix (ai, j) satisfies the condition that ai, j aa--1, j--1 + ai--1, j (mod 2) for each 1 < i < j ≤ n. It is clear that a Steinhaus graph is determined by its first row. In [3] Bringham and Dutton conjecture that almost all Steinhaus graphs have diameter 2. That is, as n approaches infinity, the ratio of the number of Steinhaus graphs with n vertices having diameter 2 to the total number of Steinhaus graphs approaches 1. Here we prove Bringham and Dutton's conjecture.

Let T be a tree with line graph T*. Define K = 21 + A(T*), where A denotes the adjacency matrix. Then the eigenvalues of -2 K-’ interlace the eigenvalues of the distance matrix D. This permits numerous results about the spectrum of K to be transcribed for the less tractable D.

For the class of 2-diregular digraphs: (1) We give a simple closed form expression—a power of 2—for the number of difactors. (2) For the adjacency matrices of these graphs, we show an intimate relationship between the permanent and determinant. (3) We give a necessary and sufficient condition for the Cartesian product of two directed circuits to have a difactor with exactly k components thereby generalizing a result of Trotter and Erdoos. Our results also show that a conjecture of Bondy, regarding vertex-transitive graphs, fails to hold for vertex-transitive digraphs.

Given a family F of ordered pairs of sets {(Su, Tu): U∈V}, the intersection digraph of F is the digraph with vertices V defined by UV∈E(D)if and only if Su∩Tv ¬= O. Interval digraphs are intersection digraphs of families in which every set is an interval, and were characterized in a previous paper by conditions on the adjacency matrix. In this paper, another such condition leads to an adjacency matrix characterization of circular-arc digraphs, the intersection digraphs of families in which every set is an arc of a circle

Intersection digraphs analogous to undirected intersection graphs are introduced. Each vertex is assigned an ordered pair of sets, with a directed edge uv in the intersection digraph when the “source set” of u intersects the “terminal set” of v. Every n-vertex digraph is an intersection digraph of ordered pairs of subsets of an n-set, but not every digraph is an intersection digraph of convex sets in the plane. Interval digraphs are those having representations where all sets are intervals on the real line. Interval digraphs are characterized in terms of the consecutive ones property of certain matrices, in terms of the adjacency matrix and in terms of Ferrers digraphs. In particular, they are intersections of pairs of Ferrers digraphs whose union is a complete digraph.

Given any integer t ≥ 2 and any prime number p, a graph Γp,t is constructed whose adjacency matrix is nilpotent of index t over Zp' the field of p elements.

A network is cycle balanced if the product of the weights (nonzero real numbers) of the lines of every cycle in it is positive. In this paper, we prove that a network D is cycle balanced if and only if its adjacency matrix is isospectral with its nonnegative counterpart. Consequent to this theorem is an analogous criterion for structural balance in sigraphs (abbreviation for “signed graphs”) as also for cycle balance in signed digraphs. These criteria establish in a natural way a wide scope for cospectrality considerations in the classes of signed digraphs and sigraphs.

It has been conjectured by C. van Nuffelen that the chromatic number of any graph with at least one edge does not exceed the rank of its adja- cency matrix. We give a counterexample, with chromatic number 32 and with an adjacency matrix of rank 29.

In this paper we introduce the notion of strongly connected polygons in the line graph of a bipartite graph. We use this notion to give a necessary and sufficient condition for a matrix Y to be fully irreducible without the need to construct a transversal of Y. In addition, we show that the notion of strongly connected polygons forms the basis of a general theory that may be used for finding all the cycles in the directed graph of a fully irreducible matrix and for constructing all the nonzero transversals of a fully irreducible matrix.