Distance–regular graphs having the M-property

We analyse when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is an M-matrix; that is, it has non-positive off-diagonal elements or, equivalently when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is also the combinatorial Laplacian of another network. When this occurs we say that the distance–regular graph has the M-property. We prove that only distance–regular graphs with diameter up to three can have the M-property and we give a characterization of the graphs that satisfy the M-property in terms of their intersection array. Moreover, we exhaustively analyse strongly regular graphs having the M-property and we give some families of distance–regular graphs with diameter three that satisfy the M-property. Roughly speaking, we prove that all distance–regular graphs with diameter one; about half of the strongly regular graphs; only some imprimitive distance–regular graphs with diameter three, and no distance–regular graphs with diameter greater than three, have the M-property. In addition, we conjecture that no primitive distance–regular graph with diameter three has the M-property.     

Reeb graphs of curves are stable under function perturbations

Reeb graphs provide a method to combinatorially describe the shape of a manifold endowed with a Morse function. One question deserving attention is whether Reeb graphs are robust against function perturbations. Focusing on one‐dimensional manifolds, we define an editing distance between Reeb graphs of curves, in terms of the cost necessary to transform one graph into another through editing moves. Our main result is that changes in Morse functions induce smaller changes in the editing distance between Reeb graphs of curves, implying stability of Reeb graphs under function perturbations. We also prove that our editing distance is equal to the natural pseudo‐distance and, moreover, that it is lower bounded by the bottleneck distance of persistent homology. Copyright © 2012 John Wiley & Sons, Ltd.     

Distance spectra and distance energy of integral circulant graphs

The distance energy of a graph G is a recently developed energy-type invariant, defined as the sum of absolute values of the eigenvalues of the distance matrix of G. There was a vast research for the pairs and families of non-cospectral graphs having equal distance energy, and most of these constructions were based on the join of graphs. A graph is called circulant if it is Cayley graph on the circulant group, i.e. its adjacency matrix is circulant. A graph is called integral if all eigenvalues of its adjacency matrix are integers. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer. In this paper, we characterize the distance spectra of integral circulant graphs and prove that these graphs have integral eigenvalues of distance matrix D. Furthermore, we calculate the distance spectra and distance energy of unitary Cayley graphs. In conclusion, we present two families of pairs (G₁,G₂) of integral circulant graphs with equal distance energy - in the first family G₁ is subgraph of G₂, while in the second family the diameter of both graphs is three.     

Bipartite almost distance-hereditary graphs

The notion of distance-heredity in graphs has been extended to construct the class of almost distance-hereditary graphs (an increase of the distance by one unit is allowed by induced subgraphs). These graphs have been characterized in terms of forbidden induced subgraphs [M. Aïder, Almost distance-hereditary graphs, Discrete Math. 242 (1–3) (2002) 1–16]. Since the distance in bipartite graphs cannot increase exactly by one unit, we have to adapt this notion to the bipartite case.In this paper, we define the class of bipartite almost distance-hereditary graphs (an increase of the distance by two is allowed by induced subgraphs) and obtain a characterization in terms of forbidden induced subgraphs.     

On the distance and distance signless Laplacian spectral radii of bicyclic graphs

The unique graphs with minimum and second-minimum distance (distance signless Laplacian, respectively) spectral radii are determined among bicyclic graphs with fixed number of vertices.     

Distance Integral Complete Multipartite Graphs with s=5, 6

Let D(G) = (dij )n×n denote the distance matrix of a connected graph G with order n, where dij is equal to the distance between vertices vi and vj in G. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In 2014, Yang and Wang gave a su?cient and necessary condition for complete r-partite graphs Kp1,p2,··· ,pr =Ka1·p1,a2·p2,··· ,as···ps to be distance integral and obtained such distance integral graphs with s = 1, 2, 3, 4. However distance integral complete multipartite graphs Ka1·p1,a2·p2,··· ,as·ps with s>4 have not been found. In this paper, we find and construct some infinite classes of these distance integral graphs Ka1·p1,a2·p2,··· ,as·ps with s = 5, 6. The problem of the existence of such distance integral graphs Ka1·p1,a2·p2,··· ,as·ps with arbitrarily large number s remains open.     

Distance graphs with large chromatic number and without large cliques

The present paper is devoted to the study of the properties of distance graphs in Euclidean space. We prove, in particular, the existence of distance graphs with chromatic number of exponentially large dimension and without cliques of dimension 6. In addition, under a given constraint on the cardinality of the maximal clique, we search for distance graphs with extremal large values of the chromatic number. The resulting estimates are best possible within the framework of the proposed method, which combines probabilistic techniques with the linear-algebraic approach.     

Distance regular graphs arising from dimensional dual hyperovals

In [12], A. Pasini and S. Yoshiara studied the distance regular graphs constructed from the Yoshiara dual hyperovals. In this note, we prove that the incidence graphs of the semibiplanes constructed from dimensional dual hyperovals are distance regular graphs if the dual hyperovals are doubly dual hyperovals (DDHOs). This generalizes the result in [12].     

Distance edge-colourings and matchings

We consider a distance generalisation of the strong chromatic index and the maximum induced matching number. We study graphs of bounded maximum degree and Erd?s–Rényi random graphs. We work in three settings. The first is that of a distance generalisation of an Erd?s–Ne?et?il problem. The second is that of an upper bound on the size of a largest distance matching in a random graph. The third is that of an upper bound on the distance chromatic index for sparse random graphs. One of our results gives a counterexample to a conjecture of Skupień.     

Distance degrees of vertex-transitive graphs

In [4], a lower bound of distance degrees of distance degree regular graphs is obtained. In this paper, we prove that a lower bound will be improved in some cases of vertex-transitive graphs.     

若干图的卡氏积的距离谱和距离能量(英文)

G是顶点集为{v_1,v_2,…,v_n}的连通简单图,G_1,G_2,…,G_n是有限图。联并图G[G_1,G_2,…,G_n】是按如下方式在G_1UG_2U…UG_n上加边而成的图:在G_i和G_j之间的任何两个顶点间加边,若v_i和v_j在G中相邻.[7]给出了两个距离正则图的卡氏积的距离谱.本文计算了联并图和距离正则图的卡氏积及两个联并图的卡氏积的距离谱.在此基础之上,我们得到了两个利用联并图与非同谱距离正则等能量图作卡氏积及联并图作卡氏积构造非同谱等距离能量图族的方法.     

Constructing 5-chromatic unit distance graphs embedded in the Euclidean plane and two-dimensional spheres

This paper is devoted to the development of algorithms for finding unit distance graphs with chromatic number greater than 4, embedded in a two-dimensional sphere or plane. Such graphs provide a lower bound for the Hadwiger–Nelson problem on the chromatic number of the plane and its generalizations to the case of the sphere. A series of 5-chromatic unit distance graphs on 64513 vertices embedded into the plane is constructed. Unlike previously known examples, these graphs do not use the Moser spindle as the base element. The construction of 5-chromatic graphs embedded in a sphere at two values of the radius is given. Namely, the 5-chromatic unit distance graph on 372 vertices embedded into the circumsphere of an icosahedron with a unit edge length, and the 5-chromatic graph on 972 vertices embedded into the circumsphere of a great icosahedron are constructed.     

Geometric aspects of 2-walk-regular graphs

A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarte?s clique bound to 1-walk-regular graphs, Godsil?s multiplicity bound and Terwilliger?s analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show.     

Trivalent orbit polynomial graphs

We introduce orbit polynomial graphs, and discuss their connections with distance- transitive, distance-regular, and distance polynomial graphs. After some general results, we classify all of the nonsymmetric trivalent orbit polynomial graphs.     

On the distance spectral radius of bipartite graphs

In this paper, we determine the unique graph with minimum distance spectral radius among all connected bipartite graphs of order $n$ with a given matching number. Moreover, we characterize the graphs with minimal distance spectral radius in the class of all connected bipartite graphs with a given vertex connectivity.     

具有最小度距离的双圈图

记G（n）为所有n阶连通简单双圈图所构成的集合．本文主要讨论G（n）按其度距离从小到大进行排序的问题，并确定了该序的前两个图及其相应的度距离，其中具有最小度距离的图是由星图K1,n-1的一个悬挂点与另外两个悬挂点之间各连上一条边所得的图Sn．     

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.     

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.     

The graphs with exactly two distance eigenvalues different from $$$$ and $$-3$$-3

In this paper, we completely characterize the graphs with third largest distance eigenvalue at most \(-1\) and smallest distance eigenvalue at least \(-3\). In particular, we determine all graphs whose distance matrices have exactly two eigenvalues (counting multiplicity) different from \(-1\) and \(-3\). It turns out that such graphs consist of three infinite classes, and all of them are determined by their distance spectra. We also show that the friendship graph is determined by its distance spectrum.