On thek-th largest eigenvalue of the Laplacian matrix of a graph

In this paper, we give the upper bound and lower bound ofk-th largest eigenvalue λk of the Laplacian matrix of a graphG in terms of the edge number ofG and the number of spanning trees ofG. This research is supported by the National Natural Science Foundation of China (Grant No.19971086) and the Doctoral Program Foundation of State Education Department of China.     

On symmetric incidence matrices of projective planes

We investigate the incidence matrix of a finite plane of ordern which admits a (C, L)-transitivityG. The elation groupG affords a generalized Hadamard matrixH=(h _ij ) of ordern and an incidence matrix for the plane is completely determined by the matrixR(H)=(R(h _ij )), whereR(g) denotes the regular permutation matrix forgG. We prove that in the caseR(H) is symmetric thatG is an elementary abelian 2-group or elseG is a nonabelian group andn is a square. Results are obtained in the abelian case linking the roots of the incidence matrixR(H) to the roots of the complex matrix (H), a nontrivial character ofG.     

Greatest common divisors and least common multiples of graphs

A graphH divides a graphG, writtenH|G, ifG isH-decomposable. A graphG without isolated vertices is a greatest common divisor of two graphsG ₁ andG ₂ ifG is a graph of maximum size for whichG|G ₁ andG|G ₂, while a graphH without isolated vertices is a least common multiple ofG ₁ andG ₂ ifH is a graph of minimum size for whichG ₁|H andG ₂|H. It is shown that every two nonempty graphs have a greatest common divisor and least common multiple. It is also shown that the ratio of the product of the sizes of a greatest common divisor and least common multiple ofG ₁ andG ₂ to the product of their sizes can be arbitrarily large or arbitrarily small. Sizes of least common multiples of various pairsG ₁,G ₂ of graphs are determined, including when one ofG ₁ andG ₂ is a cycle of even length and the other is a star.G. C's research was supported in part by the Office of Naval Research, under Grant N00014-91-I-1060     

Eigenvalues,diameter, and mean distance in graphs

It is well-known that the second smallest eigenvalue ₂ of the difference Laplacian matrix of a graphG is related to the expansion properties ofG. A more detailed analysis of this relation is given. Upper and lower bounds on the diameter and the mean distance inG in terms of ₂ are derived.This work was supported in part by the Research Council of Slovenia, Yugoslavia. A part of the work was done while the author was visiting the Ohio State University, supported by a Fulbright grant.     

A graph theoretic approach to matrix inversion by partitioning

LetM be a square matrix whose entries are in some field. Our object is to find a permutation matrixP such thatPM P ^–1 is completely reduced, i.e., is partitioned in block triangular form, so that all submatrices below its diagonal are 0 and all diagonal submatrices are square and irreducible. LetA be the binary (0, 1) matrix obtained fromM by preserving the 0's ofM and replacing the nonzero entries ofM by 1's. ThenA may be regarded as the adjacency matrix of a directed graphD. CallD strongly connected orstrong if any two points ofD are mutually reachable by directed paths. Astrong component ofD is a maximal strong subgraph. Thecondensation D ^* ofD is that digraph whose points are the strong components ofD and whose lines are induced by those ofD. By known methods, we constructD ^* from the digraph,D whose adjacency matrixA was obtained from the original matrixM. LetA ^* be the adjacency matrix ofD ^*. It is easy to show that there exists a permutation matrixQ such thatQA ^* Q ^–1 is an upper triangular matrix. The determination of an appropriate permutation matrixP from this matrixQ is straightforward.This was an informal talk at the International Symposium on Matrix Computation sponsored by SIAM and held in Gatlinburg, Tennessee, April 24–28, 1961 and was an invited address at the SIAM meeting in Stillwater, Oklahoma on August 31, 1961     

A note on unimodular congruence of the Laplacian matrix of a graph

Let G be a simple connected graph and L(G) be its Laplacian matrix. In this note, we prove that L(G) is congruent by a unimodular matrix to its Smith normal form if and only if G is a tree.     

On the Fiedler vectors of graphs that arise from trees by Schur complementation of the Laplacian

The utility of Fiedler vectors in interrogating the structure of graphs has generated intense interest and motivated the pursuit of further theoretical results. This paper focuses on how the Fiedler vectors of one graph reveal structure in a second graph that is related to the first. Specifically, we consider a point of articulation r in the graph G whose Laplacian matrix is L and derive a related graph G_{r} whose Laplacian is the matrix obtained by taking the Schur complement with respect to r in L. We show how Fiedler vectors of G_{r} relate to the structure of G and we provide bounds for the algebraic connectivity of G_{r} in terms of the connected components at r in G. In the case where G is a tree with points of articulation rR, we further consider the graph G_R derived from G by taking the Schur complement with respect to R in L. We show that Fiedler vectors of G_R valuate the pendent vertices of G in a manner consistent with the structure of the tree.     

Odd cycles and matrices with integrality properties

A cycle of a bipartite graphG(V⁺, V^?; E) is odd if its length is 2 (mod 4), even otherwise. An odd cycleC is node minimal if there is no odd cycleC′ of cardinality less than that ofC′ such that one of the following holds:C′ ∩V ⁺ ?C ∩V ⁺ orC′ ∩V ^? ?C ∩V ^?. In this paper we prove the following theorem for bipartite graphs: For a bipartite graphG, one of the following alternatives holds:

-All the cycles ofG are even.

-G has an odd chordless cycle.

-For every node minimal odd cycleC, there exist four nodes inC inducing a cycle of length four.

-An edge (u, v) ofG has the property that the removal ofu, v and their adjacent nodes disconnects the graphG.

To every (0, 1) matrixA we can associate a bipartite graphG(V⁺, V^?; E), whereV ⁺ andV ^? represent respectively the row set and the column set ofA and an edge (i,j) belongs toE if and only ifa _ij = 1. The above theorem, applied to the graphG(V⁺, V^?; E) can be used to show several properties of some classes of balanced and perfect matrices. In particular it implies a decomposition theorem for balanced matrices containing a node minimal odd cycleC, having the property that no four nodes ofC induce a cycle of length 4. The above theorem also yields a proof of the validity of the Strong Perfect Graph Conjecture for graphs that do not containK ₄?e as an induced subgraph.     

Greatest common subgraphs with specified properties

A graphG without isolated vertices is a greatest common subgraph of a setG of graphs, all having the same size, ifG is a graph of maximum size that is isomorphic to a subgraph of every graph inG. A number of results concerning greatest common subgraphs are presented. For several graphical propertiesP, we discuss the problem of determining, for a given graphG with propertyP, the existence of two non-isomorphic graphsG ₁ andG ₂ of equal size, also with propertyP, such thatG is the unique greatest common subgraph ofG ₁ andG ₂. In particular, this problem is solved whenP is the property of being 2-connected and whenP is the property of having chromatic numbern.     

Reconstruction of the set of branches of a graph

It is proved that the set of branches of a graphG is reconstructible except in a very special case. More precisely the set of branches of a graphG is reconstructible unless all the following hold: (1) the pruned center ofG is a vertex or an edge, (2)G has exactly two branches, (3) one branch contains all the vertices of degree one ofG and the other branch contains exactly one end-block. This is the best possible result in the sense that in the special excluded case, the reconstruction of the set of branches is equivalent to the reconstruction of the graph itself.1991Mathematics Subject Classification. Primary 05C60.     

On galois groups and their maximal 2-subgroups

LetG be a finite group of even order, having a central element of order 2 which we denote by −1. IfG is a 2-group, letG be a maximal subgroup ofG containing −1, otherwise letG be a 2-Sylow subgroup ofG. LetH=G/{±1} andH=G/{±1}. Suppose there exists a regular extensionL ₁ of ℚ(T) with Galois groupG. LetL be the subfield ofL ₁ fixed byH. We make the hypothesis thatL ₁ admits a quadratic extensionL ₂ which is Galois overL of Galois groupG. IfG is not a 2-group we show thatL ₁ then admits a quadratic extension which is Galois over ℚ(T) of Galois groupG and which can be given explicitly in terms ofL ₂. IfG is a 2-group, we show that there exists an element α ε ℚ(T) such thatL ₁ admits a quadratic extension which is Galois over ℚ(T) of Galois groupG if and only if the cyclic algebra (L/ℚ(T).a) splits. As an application of these results we explicitly construct several 2-groups as Galois groups of regular extensions of ℚ(T).     

A new approach to the linearity of testing planarity of graphs

In testing planarity of graphs, there are many criteria. The earliest one as known is the Kuratowski's theorem, then Whitney's, Maclane's, and so forth. Since the early sixties, people have begun researches on algorithms. Up to 1974, Hopcroft and Tarjan found an algorithm with a computing time being a linear function of the order of a graph. This is the linearity concerned here.This paper presents a new approach to the linearity by means of transforming the problem of testing planarity of a graphG into that of finding a spanning tree on another graphH, called an auxiliary graph ofG, with the order ofH being a linear function of that ofG. And moreover, we can also make the size ofH be a linear function of that ofG. The whole procedure is based on the building up of a theory of linear equations onGF (2) related toG.This was a report invited by RUTCOR, The State University of New Jersey, Rutgers, U. S. A. in 1984. And, the main part of this paper was completed during the author's stay at the Department of C & O, University of Waterloo, Canada.     

Finite modules over non-semisimple group rings

LetG be a fixed graph and letX _G be the number of copies ofG contained in the random graphG(n, p). We prove exponential bounds on the upper tail ofX _G which are best possible up to a logarithmic factor in the exponent. Our argument relies on an extension of Alon’s result about the maximum number of copies ofG in a graph with a given number of edges. Similar bounds are proved for the random graphG(n, M) too. Research of the second author supported by KBN grant 2 P03A 027 22. Research of the third author supported by KBN grant 2 P03A 15 23.     

Graphs isomorphic to subgraphs of their iterated line graphs

A graphG is said to be embeddable into a graphH, if there is an isomorphism ofG into a subgraph ofH. It is shown in this paper that every unicycle or tree which is neither a path norK _1,3 embeds in itsn-th iterated line graph forn1 or 2, 3, and that every other connected graph that embeds in itsn-th iterated line graph may be constructed from such an embedded unicycle or tree in a natural way. A special kind of embedding of graph into itsn-th iterated line graph, called incidence embedding, is studied. Moreover, it is shown that for every positive integerk, there exists a graphG such that (G) = , where (G) is the leastn1 for whichG embeds inL ⁿ(G).     

Pivoting techniques for symmetric Gaussian elimination

Summary In order to factorize an indefinite symmetric matrixG of the formG=LDL ^T whereL is a trivially invertible matrix andD is a diagonal matrix, we introduce a new kind of pivoting operation. The algorithm suggested maintains the stability and efficiency of the standard Cholesky decomposition whileG need not be positive definite. The problem of factorizingG+uu ^T whereu is a vector, scalar and the factors ofG are known, is also discussed.This research was supported in part by the Israeli National Council for Research and Development     

On the power of a perturbation for testing non-isomorphism of graphs

In this paper we prove an inverted version of A. J. Schwenk's result, which in turn is related to Ulam's reconstruction conjecture. Instead of deleting vertices from an undirected graphG, we add a new vertexv and join it to all other vertices ofG to get a perturbed graphG+v. We derive an expression for the characteristic polynomial of the perturbed graphG+v in terms of the characteristic polynomial of the original graphG. We then show the extent to which the characteristic polynomials of the perturbed graphs can be used in determining whether two graphs are non-isomorphic.This work was supported by the U.S. Army Research Office under Grant DAAG29-82-K-0107.     

H-extension of graphs

We consider the problem of constructing a graphG* from a collection of isomorphic copies of a graphG in such a way that for every two copies ofG, either no vertices or a section graph isomorphic to a graphH is identified. It is shown that ifG can be partitioned into vertex-disjoint copies ofH, thenG* can be made to have at most |H| orbits. A condition onG so thatG* can be vertextransitive is also included.     

A generalization of menger's theorem for certain block—cactus graphs

A graphG is called a block—cactus graph if each block ofG is complete or a cycle. In this paper, we shall show that a block—cactus graphG has the property that the cardinality of a smallest set separating any vertex setJ ofG is the maximum number of internally disjoint paths between the vertices ofJ if and only if every block ofG contains at most two cut-vertices. This result extends two theorems of Sampathkumar [4] and [5].     

On asymptotically best norms for powers of operators

In the study of the successive overrelaxation iterative method for solving large systems of linear equations, a frequently considered problem is the behavior of the norm of powers of the successive overrelaxation matrix,L _b ^m both as a function ofm and of the given norm. Our main result is a rather natural necessary and sufficient condition for the existence of a norm asymptotically best for a non-nilpotent matrixA. As a corollary of our main result, it is shown here that there isno asymptotically best norm for the successive overrelaxation matrixL _b ^m .Research supported in part by the Atomic Energy Commission under Grant AT(11-1)-2075.     

Analysis of a Distinguished Laplacian on Solvable Lie Groups

We study a class of kernels associated to functions of a distinguished Laplacian on the solvable group AN occurring in the Iwasawa decomposition G = ANK of a noncompact semisimple Lie group G. We determine the maximal ideal space of a commutative subalgebra of L¹, which contains the algebra generated by the heat kernel, and we prove that the spectrum of the Laplacian is the same on all L^p spaces, 1 ≤ p < ∞. When G is complex, we derive a formula that enables us to compute the L^p norm of these kernels in terms of a weighted L^p norm of the corresponding kernels for the Euclidean Laplacian on the tangent space. We also prove that, when G is either rank one or complex, certain Hardy-Littlewood maximal operators, which are naturally associated with these kernels, are weak type (1, 1).