The incidence matrix and labelings of a graph

We deal with the problem of labeling the edges of a graph in such a way that the labels of the edges incident with any vertex add up to a value prescribed for that vertex. We show that the use of elementary column operations on the incidence matrix is fruitful in giving easy proofs of theorems on magic graphs and labeling |1, 3, 4|. The method can be visualized in the graph and also leads to a simple proof of a theorem in |2| on the multiplicity of −2 as an eigenvalue of a line graph. We also deal with mixed graphs, the label of a directed edge being subtracted at its initial vertex.     

On incidence energy of a graph

The Laplacian-energy like invariant LEL(G) and the incidence energy IE(G) of a graph are recently proposed quantities, equal, respectively, to the sum of the square roots of the Laplacian eigenvalues, and the sum of the singular values of the incidence matrix of the graph G. However, IE(G) is closely related with the eigenvalues of the Laplacian and signless Laplacian matrices of G. For bipartite graphs, IE=LEL. We now point out some further relations for IE and LEL: IE can be expressed in terms of eigenvalues of the line graph, whereas LEL in terms of singular values of the incidence matrix of a directed graph. Several lower and upper bounds for IE are obtained, including those that pertain to the line graph of G. In addition, Nordhaus-Gaddum-type results for IE are established.     

On the number of unique subgraphs of a graph

A question of Entringer and Erdös concerning the number of unique subgraphs of a graph is answered.     

The perturbed laplacian matrix of a graph

For a graph G, we define its perturbed Laplacian matrix as D?A(G) where A(G) is the adjacency matrix of G and D is an arbitrary diagonal matrix. Both the Laplacian matrix and the negative of the adjacency matrix are special instances of the perturbed Laplacian. Several well-known results, contained in the classical work of Fiedler and in more recent contributions of other authors are shown to be true, with suitable modifications, for the perturbed Laplacian. An appropriate generalization of the monotonicity property of a Fiedler vector for a tree is obtained. Some of the results are applied to interval graphs.     

Search for properties of the missing Moore graph

In the degree-diameter problem, the only extremal graph the existence of which is still in doubt is the Moore graph of order 3250, degree 57 and diameter 2. It has been known that such a graph cannot be vertex-transitive. Also, certain restrictions on the structure of the automorphism group of such a graph have been known in the case when the order of the group is even. In this paper we further investigate symmetries and structural properties of the missing Moore (57, 2)-graph(s) with the help of a combination of spectral, group-theoretic, combinatorial, and computational methods. One of the consequences is that the order of the automorphism group of such a graph is at most 375.     

General Variable Neighborhood Search for computing graph separators

Computing graph separators in networks has a wide range of real-world applications. For instance, in telecommunication networks, a separator determines the capacity and brittleness of the network. In the field of graph algorithms, the computation of balanced small-sized separators is very useful, especially for divide-and-conquer algorithms. In bioinformatics and computational biology, separators are required in grid graphs providing a simplified representation of proteins. This papers presents a new heuristic algorithm based on the Variable Neighborhood Search methodology for computing vertex separators. We compare our procedure with the state-of-the-art methods. Computational results show that our procedure obtains the optimum solution in all of the small and medium instances, and high-quality results in large instances.     

On the adjacency matrix of a threshold graph

A threshold graph on n   vertices is coded by a binary string of length n−1$n-1$. We obtain a formula for the inertia of (the adjacency matrix of) a threshold graph in terms of the code of the graph. It is shown that the number of negative eigenvalues of the adjacency matrix of a threshold graph is the number of ones in the code, whereas the nullity is given by the number of zeros in the code that are preceded by either a zero or a blank. A formula for the determinant of the adjacency matrix of a generalized threshold graph and the inverse, when it exists, of the adjacency matrix of a threshold graph are obtained. Results for antiregular graphs follow as special cases.     

On the distance matrix of a directed graph

In this note, we show how the determinant of the distance matrix D(G) of a weighted, directed graph G can be explicitly expressed in terms of the corresponding determinants for the (strong) blocks G_i of G. In particular, when cof D(G), the sum of the cofactors of D(G), does not vanish, we have the very attractive formula .     

A unique graph of minimal elastic energy

Nonlinear functionals that appear as a product of two integrals are considered in the context of elastic curves of variable length. A technique is introduced that exploits the fact that one of the integrals has an integrand independent of the derivative of the unknown. Both the linear and the nonlinear cases are illustrated. By lengthening parameterized curves it is possible to reduce the elastic energy to zero. It is shown here that for graphs this is not the case. Specifically, there is a unique graph of minimal elastic energy among all graphs that have turned 90 degrees after traversing one unit.

     

The scattering matrix with respect to an Hermitian matrix of a graph

Recently, Gnutzmann and Smilansky [5] presented a formula for the bond scattering matrix of a graph with respect to an Hermitian matrix. We present another proof for this formula by a technique use in the zeta function of a graph. Furthermore, we generalize Gnutzmann and Smilansky's formula to a regular covering of a graph. Finally, we define an L-function of a graph, and present a determinant expression. As a corollary, we express the generalization of Gnutzmann and Smilansky's formula to a regular covering of a graph by using its L-functions.     

Complex eigenvalues of a non-negative matrix with a specified graph

Let A be a non-negative matrix of order n with Perron eigenvalue ? and associated directed graph G. Let m be the length of the longest circuit of G. Theorem: If m=2, all eigenvalues of A are real. If 2<m?n, and if λ=μ+iv is an eigenvalue of A, then $\text{μ+|v|tan(}\text{Π}\text{m}\text{) ? ρ}$.     

Inverse of the distance matrix of a block graph

A connected graph G, whose 2-connected blocks are all cliques (of possibly varying sizes) is called a block graph. Let D be its distance matrix. By a theorem of Graham, Hoffman and Hosoya, we have det(D)?≠?0. We give a formula for both the determinant and the inverse, D ^?1 of D.     

The laplacian matrix of a graph: unimodular congruence

This paper gives graph-theoretic conditions that are sufficient for the Laplaceman matrices of two graphs to be congruent by a unimodular matrix.     

The laplacian matrix of a graph: unimodular congruence

This paper gives graph-theoretic conditions that are sufficient for the Laplaceman matrices of two graphs to be congruent by a unimodular matrix.     

Some results on the incidence coloring number of a graph

This paper proves that if G is a cubic graph which has a Hamiltonian path or G is a bridgeless cubic graph of large girth, then its incidence coloring number is at most 5. By relating the incidence coloring number of a graph G to the chromatic number of G², we present simple proofs of some known results, and characterize regular graphs G whose incidence coloring number equals Δ(G)+1.     

The Terwilliger algebra of the incidence graph of the Hamming graph

Let \(\varGamma \) be a distance-semiregular graph on Y, and let \(D^Y\) be the diameter of \(\varGamma \) on Y. Let \(\varDelta \) be the halved graph of \(\varGamma \) on Y. Fix \(x \in Y\). Let T and \(T'\) be the Terwilliger algebras of \(\varGamma \) and \(\varDelta \) with respect to x, respectively. Assume, for an integer i with \(1 \le 2i \le D^Y\) and for \(y,z \in \varGamma _{2i}(x)\) with \(\partial _{\varGamma }(y,z)=2\), the numbers \(|\varGamma _{2i-1}(x) \cap \varGamma (y) \cap \varGamma (z)|\) and \(|\varGamma _{2i+1}(x) \cap \varGamma (y) \cap \varGamma (z)|\) depend only on i and do not depend on the choice of y, z. The first goal in this paper is to show the relations between T-modules of \(\varGamma \) and \(T'\)-modules of \(\varDelta \). Assume \(\varGamma \) is the incidence graph of the Hamming graph H(D, n) on the vertex set Y and the set \({\mathcal {C}}\) of all maximal cliques. Then, \(\varGamma \) satisfies above assumption and \(\varDelta \) is isomorphic to H(D, n). The second goal is to determine the irreducible T-modules of \(\varGamma \). For each irreducible T-module W, we give a basis for W the action of the adjacency matrix on this basis and we calculate the multiplicity of W.