CanaDAM 2021
En ligne, 25 - 28 mai 2021

Distances in graphs

AYSEL EREY, Gebze Technical University
Chromatic number and distance spectral radius  [PDF]

The distance spectral radius of a graph is the largest eigenvalue of its distance matrix. We discuss the problem of maximizing the distance spectral radius of a connected graph with fixed chromatic number and order, and we determine the unique extremal graph among all connected $4$-chromatic planar graphs of fixed order.

AHMAD MOJALLAL, University of Regina
The minimum number of distinct eigenvalues of threshold graphs  [PDF]

For a graph $G$, we associate a family of real symmetric matrices, $S(G)$, where for any $M \in S(G)$, the location of the nonzero off-diagonal entries of $M$ are governed by the adjacency structure of $G$. The minimum number of distinct eigenvalues, taken over $S(G)$ compatible with the graph $G$ is denoted by $q(G)$.

Threshold graphs can be characterized in many ways. One way of obtaining a threshold graph is through an iterative process that starts with an isolated vertex, and where, at each step, either a new isolated vertex is added, or a vertex adjacent to all previous vertices (dominating vertex) is added.

In this talk, we study the spectral invariant of $q(G)$ for connected threshold graphs of a fixed order $n$.

JESMINA PERVIN, Indian Institute of Technology( Banaras Hindu University), Varanasi
Q-integral connected graphs with maximum edge-degrees less than or equal to 8  [PDF]

Graphs with integral signless Laplacian spectrum are called $Q$-integral graphs. The number of adjacent edges to an edge defines the edge-degree of that edge. The $Q$-spectral radius of a graph is the largest eigenvalue of its signless Laplacian. In 2019, Jongyook Park and Yoshio Sano studied $Q$-integral connected graphs with edge-degrees at most six. In this article, we extend this result and study the $Q$-integral connected graph with maximum edge-degree less than or equal to eight. Further, we give an upper and lower bound for the maximum edge-degree of a $Q$-integral connected graph with respect to its $Q$-spectral radius. As a corollary, we also show that the $Q$-spectral radius of the edge-non-regular $Q$-integral connected graph with maximum edge-degree five is six which we anticipate to be a key for solving the unsolved problem of characterizing such graphs.

SANJA RUKAVINA, Department of Mathematics, University of Rijeka, Croatia
Self-orthogonal codes from equitable partitions of distance-regular graphs  [PDF]

We give two methods for a construction of self-orthogonal codes using equitable partitions of distance-regular graphs. In the case of 2-class association schemes one of the methods coincides with the construction from strongly regular graphs given in [1], and in the case when all cells of the partition are of the same size it coincides with the construction presented in [2]. We apply these methods to construct self-orthogonal codes from some distance-regular graphs.

This is a joint work with Dean Crnković and Andrea Švob.


[1] Crnković, D., Maksimović, M., Rodrigues, B. G., Rukavina, S.: Self-orthogonal codes from the strongly regular graphs on up to 40 vertices, Adv. Math. Commun. 10 (2016), 555-582.

[2] Crnković, D., Rukavina, S., Švob, A.: Self-orthogonal codes from equitable partitions of association schemes, ArXiv preprint,

On some classes of vertex-transitive distance-regular antipodal covers of complete graphs  [PDF]

Distance-regular antipodal cover of a complete graph (called briefly an $(n, r, \mu)$-cover) is equivalently defined as a graph whose vertex set admits a partition into $n$ cells of the same size $r$ such that (i) each its cell induces a $r$-coclique, (ii) the union of any two distinct cells induces a perfect matching, and (iii) any two non-adjacent vertices that lie in distinct cells have exactly $\mu$ common neighbors. In general, such graphs do not have a universal construction, and one of most important tasks in their study is to classify $(n, r, \mu)$-covers with vertex-transitive automorphism groups. In this talk, I will present some recent results on construction and classification of $(n, r, \mu)$-covers with vertex-transitive automorphism groups of some special types.