On signed graphs with just two distinct adjacency eigenvalues

In this paper, all simple connected signed graphs with maximum degree at most 4 and with just two distinct adjacency eigenvalues are completely characterized, there exists an infinite family of 4-regular signed graphs with just two distinct adjacency eigenvalues.     

Strong chromatic index of unit distance graphs

The strong chromatic index of a graph , denoted by , is defined as the least number of colors in a coloring of edges of , such that each color class is an induced matching (or: if edges and have the same color, then both vertices of are not adjacent to any vertex of ). A graph is a unit distance graph in if vertices of can be uniquely identified with points in , so that is an edge of if and only if the Euclidean distance between the points identified with and is 1. We would like to find the largest possible value of , where is a unit distance graph (in and ) of maximum degree . We show that , where is a unit distance graph in of maximum degree . We also show that the maximum possible size of a strong clique in unit distance graph in is linear in and give a tighter result for unit distance graphs in the plane.     

Products of unit distance graphs

Some graphs admit drawings in the Euclidean plane (k-space) in such a (natural) way, that edges are represented as line segments of unit length. We say that they have the unit distance property.The influence of graph operations on the unit distance property is discussed. It is proved that the Cartesian product preserves the unit distance property in the Euclidean plane, while graph union, join, tensor product, strong product, lexicographic product and corona do not. It is proved that the Cartesian product preserves the unit distance property also in higher dimensions.     

Adjacency matrices of probe interval graphs

In this paper we obtain several characterizations of the adjacency matrix of a probe interval graph. In course of this study we describe an easy method of obtaining interval representation of an interval bigraph from its adjacency matrix. Finally, we note that if we add a loop at every probe vertex of a probe interval graph, then the Ferrers dimension of the corresponding symmetric bipartite graph is at most 3.     

Unit gain graphs with two distinct eigenvalues and systems of lines in complex space

Since the introduction of the Hermitian adjacency matrix for digraphs, interest in so-called complex unit gain graphs has surged. In this work, we consider gain graphs whose spectra contain the minimum number of two distinct eigenvalues. Analogously to graphs with few distinct eigenvalues, a great deal of structural symmetry is required for a gain graph to attain this minimum. This allows us to draw a surprising parallel to well-studied systems of lines in complex space, through a natural correspondence to unit-norm tight frames. We offer a full classification of two-eigenvalue gain graphs with degree at most 4, or with multiplicity at most 3. Intermediate results include an extensive review of various relevant concepts related to lines in complex space, including SIC-POVMs, MUBs and geometries such as the Coxeter-Todd lattice, and many examples obtained as induced subgraphs by employing a technique parallel to the dismantling of association schemes. Finally, we touch on an innovative application of simulated annealing to find examples by computer.     

Smith normal form of some distance matrices

We determine the Smith normal form of the distance matrices of unicyclic graphs and of the wheel graph with trees attached to each vertex.     

Commutativity of the adjacency matrices of graphs

We say that two graphs G₁ and G₂ with the same vertex set commute if their adjacency matrices commute. In this paper, we find all integers n such that the complete bipartite graph K_n,n is decomposable into commuting perfect matchings or commuting Hamilton cycles. We show that there are at most n−1 linearly independent commuting adjacency matrices of size n; and if this bound occurs, then there exists a Hadamard matrix of order n. Finally, we determine the centralizers of some families of graphs.     

The distance coloring of graphs

Let G be a connected graph with maximum degree Δ≥ 3.We investigate the upper bound for the chromatic number χγ(G) of the power graph Gγ.It was proved that χγ(G) ≤Δ(Δ-1)γ-1Δ-2+ 1 =:M + 1,where the equality holds if and only if G is a Moore graph.If G is not a Moore graph,and G satisfies one of the following conditions:(1) G is non-regular,(2) the girth g(G) ≤ 2γ- 1,(3)g(G) ≥ 2γ + 2,and the connectivity κ(G) ≥ 3 if γ≥ 3,κ(G) ≥ 4 but g(G) 6 if γ = 2,(4) Δis sufficiently larger than a given number only depending on γ,then χγ(G) ≤ M- 1.By means of the spectral radius λ1(G) of the adjacency matrix of G,it was shown that χ2(G) ≤λ1(G)2+ 1,where the equality holds if and only if G is a star or a Moore graph with diameter 2 and girth 5,and χγ(G)λ1(G)γ+1 ifγ≥3.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Long cycles and paths in distance graphs

For n∈N and D⊆N, the distance graph has vertex set {0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant c_D such that the greatest common divisor of the integers in D is 1 if and only if for every n, has a component of order at least n−c_D if and only if for every n≥c_D+3, has a cycle of order at least n−c_D. Furthermore, we discuss some consequences and variants of this result.     

Retarded regular graphs are regular or semiregular

A graph G is said to be retarded regular if there is a positive integral number s such that the number of walks of length s starting at vertices of G is a constant function. Regular and semiregular graphs are retarded regular with s?=?1 and s\!≤ \!2, respectively. We prove that any retarded regular connected graph is either regular or semiregular.