Search

The ordinary graphs of finite order ν with (−1, 1, 0) adjacency matrix A satisfying ( A − ρ 1 I ) ( A − ρ 2 I ) = (ν − 1 + ρ 1 ρ 2 ) J , ρ 1 ρ 2 , AJ= ρ 0 J . The only eigenvalues are ρ 1 , ρ 2 , ρ 0 with certain multiplicities. The numbers ρ 1 and ρ 2 turn out to be odd integers unless ρ 1 + ρ 2 = 0. Graphs satisfying the specified conditions are strong graphs. They include graphs whose (−1, 1, 0) adjacency matrix is orthogonal. Strong graphs with ν − 1 + ρ 1 ρ 2 ≠ 0 are regular. The chapter presents a more general theorem on complete bipartite induced sub graphs; most of the strongly regular graphs with ρ 1 = 3 contain no 3-claw. With this, the proof of the standard form for the adjacency matrix of graphs and of the final theorems mainly is a matter of elementary matrix multiplication.

A tetrahedral graph is defined to be a graphG, whose vertices are identified with the\(\left( {\begin{array}{*{20}c} n \\ 3 \\ \end{array} } \right)\) unordered triplets onn symbols, such that vertices are adjacent if and only if the corresponding triplets have two symbols in common. Ifn2(x) denotes the number of verticesy, which are at distance 2 fromx andA(G) denotes the adjacency matrix ofG, thenG has the following properties: P1) the number of vertices is\(\left( {\begin{array}{*{20}c} n \\ 3 \\ \end{array} } \right)\). P2)G is connected and regular. P3)n2(x) = 3/2(n−3)(n−4) for allx inG. P4) the distinct eigenvalues ofA(G) are −3, 2n−9,n−7, 3(n−3). We show that, ifn > 16, then any graphG (with no loops and multiple edges) having the properties P1)–P4) must be a tetrahedral graph. An alternative characterization of tetrahedral graphs has been given by the authors in [1].

Let G be a graph, $A(G)$ be the adjacency matrix of G, and $\lambda (G)$ the least eigenvalue of $A(G)$. Information is given about the following three quantities: \[\begin{aligned} \lambda _R (G) & = \mathop {\sup }\limits_{\substack{ H \supset G \\ H\,{\text{regular}} }} \lambda (H) \\ \mu (G) & = \mathop {\lim }\limits_{d \to \infty } \mathop {\sup }\limits_{\substack{ H \supset G \\ d(H) > d }} \mu (G) \\ \mu _R (G) & = \mathop {\lim }\limits_{d \to \infty } \mathop {\sup }\limits_{\substack{ H \supset G \\ H\,{\text{regular}} \\ d(H) > d }} \mu (G) \end{aligned} \]

The combinatorial properties of a nonnegative matrix M are captured by that binary matrix A = A(M) in which the entries are 1 whenever those of M are positive. If A is a square matrix, then it can be regarded as the adjacency matrix of a directed graph (digraph). If A is rectangular, a bipartite graph (bigraph) can be associated with A; of course this can also be done for A square. The determinant of the adjacency matrix of a graph or digraph has been expressed in terms of its structure, and so has the permanent. The purposes of this report are to express the permanent of a square or rectangular binary matrix in terms of the associated bigraph, and to formulate the determinant of a square matrix in terms of its bigraph. (Author)

Properties of a graph (directed or undirected) whose adjacency matrix is a circulant are studied. Examples are given showing that the connection set determined by the first row of such a matrix need not be multiplicatively related to the connection set of an isomorphic graph. Two different criteria are given under which two graphs with circulant adjacency matrices are isomorphic if and only if their connection sets are multiplicatively related. The first criterion is that the graphs have a prime number of vertices. The second criterion is that the adjacency matrices have non-repeated eigenvalues. The final section gives a partial characterization of graphs with n vertices whose automorphism group is the cyclic group Cn.

This paper studies the fill-in properties of Gaussian elimination on sparse random matrices. A theoretical study using the concept of random graphs yields formulae from which the fill-in can be evaluated. The predictions are examined for matrices of various orders and densities and are found to be in close agreement with experimental results. A possible consequence of the results of this paper relating to error analysis for sparse systems is given in the concluding section. 1. Introduction. This paper studies the fill-in properties of Gaussian elimina- tion on sparse random matrices. Graph theoretical ideas are introduced and the problem is examined using the concept of random graphs. This concept of using random graphs is not a new one. They are used as a tool in the development of existence theorems in graph theory (Erdos (1967)) and some work has been done on the structure of a graph where the number of lines is a function of the number of points, the analysis holding in the limit as the number of points tends to infinity (Palasti (1966, 1970)). Ogilvie (1968) has shown that these asymptotic results hold where the graph has only a small number of vertices (about 10) but none of this work is directly concerned with matrix decomposition or indeed with the adjacency matrix of the graph. Heap (1966) has extended the notion of random graphs to examine properties of their adjacency matrices. However, his Tesults on matrix reducibility are only valid for comparatively dense matrices (prob- ability density > 0.15). A serious attempt to tackle the problem of this paper has been made by Hsieh and Ghausi (1971) where they have tried to make theoretical predictions on the results of Brayton et al. (1970). Their work has, however, several serious defects. Although they make more allowance for interaction than the discus- sion in Section 2, their formulae only include correlation between elements in the same column ignoring the correlation which exists between elements in the same row. In addition, some of their formulae break down if the density of the matrix increases above 20% and their correlation factor H is chosen empirically to obtain a fit with Brayton's data rather than determined theoretically. The impetus for writing this paper came from remarks by Robert Brayton in the panel at the end of the IBM symposium (Rose and Willoughby (1972)) when he stated that the above problem, although itself not perhaps of devastating importance, has consumed vast

Various results are derived about the adjacency matrix of a tournament; in particular, it is shown that if a tournament Tn is irreducible and n>-5, then its matrix is primitive with exponent at most n+2

An algorithm is presented for constructing from the adjacency matrix of a digraph the matrix of its simplen-sequences. In this matrix, thei, j entry,i ≠j, gives the number of paths of lengthn from a pointv i to a pointv j ; the diagonal entryi, i gives the number of cycles of lengthn containingv i . The method is then generalized to networks—that is, digraphs in which some value is assigned to each line. With this generalized algorithm it is possible, for a variety of value systems, to calculate the values of the paths and cycles of lengthn in a network and to construct its value matrix of simplen-sequences. The procedures for obtaining the two algorithms make use of properties of a line digraph—that is, a derived digraph whose points and lines represent the lines and adjacency of lines of the given digraph.

Let G be a finite undirected graph with at most one edge joining a pair of vertices and no edge joining a vertex to itself. L(G) denotes the line graph of G, i.e., the vertices of L(G) are the edges of G and two vertices of L(G) are adjacent if the corresponding edges of G are adjacent. Let d(u) denote the valence of a vertex u. Let d(G) denote the smallest integer which is equal to the valence of some vertex of u. For an edge (u,v). Δ(u,v) denotes the number of vertices w which are adjacent to both u and v. The main theorem of this paper is: If (i) d(G)>43, (ii)−2 is the minimum eigenvalue of the adjacency matrix of G, and (iii) for any edge (u,v), Δ(u,v)3, the the line graph L(H) satisfies conditions (ii) and (iii) stated above.

If L ( G ) is the line graph of G , and A ( L ( G )), the adjacency matrix of L ( G ), acts on a vector x , this vector may be thought of as an integral chain of G . The eigenspace of L ( G ) determines a matroid for G . For the eigenvalue −2, this matroid has a geometric interpretation, and from this we obtain all eigenvectors corresponding to this eigenvalue. Matroids are normally considered over integral domains, and the results for eigenvectors are generalized to a geometric interpretation for all integral domains. These results are applied to the ring of complex numbers, and strict bounds for the least eigenvalue of a line graph are obtained.

Generalized inverses of matrices over the Boolean algebra of order two are investigated by using reduction techniques. These results are then applied to the study of directed graphs, given in terms of their adjacency matrix.

A (0, 1)-matrix M has the consecutive 1's property for columns if the rows of M can be permuted so that the 1's in each column appear consecutively. A graph-theoretic approach is used to characterize matrices with this property in terms of forbidden submatrices. Graphs whose adjacency matrix has this property are also characterized.

Given the adjacency matrix of the graph, the algorithm presented in this paper finds a spanning tree and then constructs the set of fundamental cycles. Our algorithm is slower than an algorithm presented by Welch by a ratio of N /3 ( N is the number of nodes) but requires less storage. For graphs with a large number of nodes and edges, when storage is limited our algorithm is superior to Welch's; however, when the graphs are small, or machine storage is very large, Welch's algorithm is superior. Timing estimates and storage requirements for both methods are presented.