Distance mean-regular graphs

We introduce the concept of distance mean-regular graph, which can be seen as a generalization of both vertex-transitive and distance-regular graphs. Let \(\Gamma \) be a graph with vertex set V, diameter D, adjacency matrix \(\varvec{A}\), and adjacency algebra \(\mathcal{A}\). Then, \(\Gamma \) is distance mean-regular when, for a given \(u\in V\), the averages of the intersection numbers \(p_{ij}^h(u,v)=|\Gamma _i(u)\cap \Gamma _j(v)|\) (number of vertices at distance i from u and distance j from v) computed over all vertices v at a given distance \(h\in \{0,1,\ldots ,D\}\) from u, do not depend on u. In this work we study some properties and characterizations of these graphs. For instance, it is shown that a distance mean-regular graph is always distance degree-regular, and we give a condition for the converse to be also true. Some algebraic and spectral properties of distance mean-regular graphs are also investigated. We show that, for distance mean regular-graphs, the role of the distance matrices of distance-regular graphs is played for the so-called distance mean-regular matrices. These matrices are computed from a sequence of orthogonal polynomials evaluated at the adjacency matrix of \(\Gamma \) and, hence, they generate a subalgebra of \(\mathcal{A}\). Some other algebras associated to distance mean-regular graphs are also characterized.     

A survey of stratified domination in graphs

A graph G is 2-stratified if its vertex set is partitioned into two nonempty classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that for every blue vertex v of G, there is a copy of F in G rooted at v. In this paper, we survey recent results on the F-domination number for various 2-stratified graphs F.     

Distance regularity in direct-product graphs

The direct product (also called Kronecker product, tensor product, and cardinal product) G × H of distance-regular graphs is investigated. It is demonstrated that the product is distance-regular only when G and H are very restricted distance-regular graphs.     

Distance degree regular graphs

In this note, inequalities between the distance degrees of distance degree regular graphs and to characterize the graphs when one of the equalities holds are proved.     

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.     

Distance paired domination numbers of graphs

In this paper, we study a generalization of the paired domination number. Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k-distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The k-distance paired domination number is the cardinality of a smallest k-distance paired dominating set of G. We investigate properties of the k-distance paired domination number of a graph. We also give an upper bound and a lower bound on the k-distance paired domination number of a non-trivial tree T in terms of the size of T and the number of leaves in T and we also characterize the extremal trees.     

Distance graphs with maximum chromatic number

The distance graph G(D) has the set of integers as vertices and two vertices are adjacent in G(D) if their difference is contained in the set D⊂Z. A conjecture of Zhu states that if the chromatic number of G(D) achieves its maximum value |D|+1 then the graph has a triangle. The conjecture is proven to be true if |D|?3. We prove that the chromatic number of a distance graph with D={a,b,c,d} is five only if either D={1,2,3,4k} or D={a,b,a+b,b-a}. This confirms a stronger version of Zhu's conjecture for |D|=4, namely, if the chromatic number achieves its maximum value then the graph contains K₄.     

Distance distributions for graphs modeling computer networks

The Wiener polynomial of a graph G is a generating function for the distance distribution dd(G)=(D₁,D₂,…,D_t), where D_i is the number of unordered pairs of distinct vertices at distance i from one another and t is the diameter of G. We use the Wiener polynomial and several related generating functions to obtain generating functions for distance distributions of unweighted and weighted graphs that model certain large classes of computer networks. These provide a straightforward means of computing distance and timing statistics when designing new networks or enlarging existing networks.     

Distance matrices,dimension, and conference graphs

We define the dimension of a distance matrix and its associated metric space, and use this to give necessary and sufficient conditions for a metric space to be isometrically embeddable into suitable real inner product spaces and Euclidean spheres. Also, for certain distance matrices C with irrational entries, we derive the bound w ≤ 2f+ 1 for the size w of C in terms of its dimension f. This result is applied to improve a bound by Larman, Rogers, and Seidel on two-distance sets in Euclidean space, and to characterize certain regular graphs as conference graphs.     

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.     

Distance monotone graphs and a new characterization of hypercubes

The aim of this paper is to study the class of s.c. distance monotone graphs which arise naturally when investigating some intersection properties of graphs. A new characterization of hypercubes is also obtained.     

Distance and routing labeling schemes for non-positively curved plane graphs

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently (e.g., in constant or logarithmic time) by merely inspecting the labels of u and v, without using any other information. Similarly, routing labeling schemes are schemes that label the vertices of a graph with short labels in such a way that given the label of a source vertex and the label of a destination, it is possible to compute efficiently (e.g., in constant or logarithmic time) the port number of the edge from the source that heads in the direction of the destination. In this paper we show that the three major classes of non-positively curved plane graphs enjoy such distance and routing labeling schemes using O(log²n) bit labels on n-vertex graphs. In constructing these labeling schemes interesting metric properties of those graphs are employed.     

Distance signless Laplacian spectral radius and Hamiltonian properties of graphs

In this paper, we establish a sufficient condition on distance signless Laplacian spectral radius for a bipartite graph to be Hamiltonian. We also give two sufficient conditions on distance signless Laplacian spectral radius for a graph to be Hamilton-connected and traceable from every vertex, respectively. Furthermore, we obtain a sufficient condition for a graph to be Hamiltonian in terms of the distance signless Laplacian spectral radius of the complement of a graph G.     

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.