Search

An eigenvalue λ of a signed graph S of order n is a main eigenvalue if its eigenspace is not orthogonal to the all-ones vector j. Characterizing signed graphs with exactly k (1 ≤ k ≤ n) main eigenvalues is a problem in algebraic and graph theory that has been studied since 2020. Z. Stanić has noticed that a signed graph has exactly one main eigenvalue if and only if it is net-regular, and in this paper, we study signed graphs with exactly two distinct main eigenvalues by studying (0 , 1 , 2) -multi-graphs with exactly two distinct main eigenvalues. We partially characterize the case when the basic graphs of the (0 , 1 , 2) -multi-graphs are trees, and propose some problems for further research. [ABSTRACT FROM AUTHOR]

In this paper, we give a characterization of regular two-graphs of order n in terms of spectral data of two-graphs of order n − 1 and n − 2. Moreover, we prove that a two-graph of order n is regular if and only if all its induced sub-two-graphs with n − 2 vertices have the same characteristic polynomial. [ABSTRACT FROM AUTHOR]

We study the problem of maximizing the number of full degree vertices in a spanning tree T of a graph G ; that is, the number of vertices whose degree in T equals its degree in G. In cubic graphs, this problem is equivalent to maximizing the number of leaves in T and minimizing the size of a connected dominating set of G. We provide an algorithm that produces (w.h.p.) a tree with at least 0. 4591 n vertices of full degree (and also, leaves) when run on a random cubic graph. This improves the previously best known lower bound of 0. 4146 n. We also provide lower bounds on the number of full degree vertices in the random regular graph G (n , r) for r ≤ 10. [ABSTRACT FROM AUTHOR]

To maximize aggregate effort, a principal allocates agents to a given graph of roles where each agent's reward is exogenously fixed and increases in the aggregate effort of their immediate neighbourhood. Effort is costly for individual agents, thus forming a local public goods game. Agents can be selfish or stubborn (following Kantian imperatives that maximize agent welfare). For regular graphs, we provide conditions under which Kantians are located in clusters or are far apart. When Kantian and isolated-selfish efforts are close, the principal's optimal allocation also maximizes agent welfare. We discuss difficulties surrounding the notion of Kantian imperatives on non-regular graphs and solve the principal's problem on graphs where roles are entirely based on degree. Our results show that, compared to standard public goods games over complete networks, organizations with Kantian agents suffer from both over- and under-provision of public goods when the underlying graph becomes relevant. [ABSTRACT FROM AUTHOR]

We consider the Laplacian on a metric graph, equipped with Robin (δ -type) vertex condition at some of the graph vertices and Neumann–Kirchhoff condition at all others. The corresponding eigenvalues are called Robin eigenvalues, whereas they are called Neumann eigenvalues if the Neumann–Kirchhoff condition is imposed at all vertices. The sequence of differences between these pairs of eigenvalues is called the Robin–Neumann gap. We prove that the limiting mean value of this sequence exists and equals a geometric quantity, analogous to the one obtained for planar domains by Rudnick et al. (Commun Math Phys, 2021. arXiv:2008.07400). Moreover, we show that the sequence is uniformly bounded and provide explicit upper and lower bounds. We also study the possible accumulation points of the sequence and relate those to the associated probability distribution of the gaps. To prove our main results, we prove a local Weyl law, as well as explicit expressions for the second moments of the eigenfunction scattering amplitudes. [ABSTRACT FROM AUTHOR]

The rank of adjacency matrix plays an important role in construction of linear codes from a directed strongly regular graph using different techniques, namely, code orthogonality, adjacency matrix determinant and adjacency matrix spectrum. The problem of computing the dimensions of such codes is an intriguing one. Several conjectures to determine the rank of adjacency matrix of a DSRG Γ over a finite field, keep researchers working in this area. To address the same to an extent, we have considered the problem of finding the rank over a finite field of the adjacency matrix of a DSRG Γ (v , k , t , λ , μ) with μ = 1 , including some mixed Moore graphs and corresponding codes arising from them, in this paper. [ABSTRACT FROM AUTHOR]

Since today's HPC and data center systems can comprise hundreds of thousands of servers and beyond, it is crucial to equip them with a network that provides high performance. New topologies proposed to achieve such performance need to be evaluated under different traffic conditions, aiming to closely replicate real-world scenarios. While most optimizations should be guided by common traffic patterns, it is essential to ensure that no pathological traffic pattern can compromise the entire system. Determining synthetic adversarial traffic patterns for a network typically relies on a thorough understanding of its topology and routing. In this paper, we address the problem of identifying a generic adversarial traffic pattern for low-diameter direct interconnection networks. We first focus on Random Regular Graphs (RRGs), which represent a typical case for these networks. Moreover, RRGs have been proposed as topologies for interconnection networks due to their superior scalability and expandability, among other advantages. We introduce Ant Mill, an adversarial traffic pattern for RRGs when using routes of minimal length. Secondly, we demonstrate that the Ant Mill traffic pattern is also adversarial in other low-diameter direct interconnection networks such as Slimfly, Dragonfly, and Projective networks. Ant Mill is thoroughly motivated and evaluated, enabling future studies of low-diameter direct interconnection networks to leverage its findings. [ABSTRACT FROM AUTHOR]

The multiplicity of an eigenvalue λ of a graph G is denoted by m (G , λ). In a connected graph G with at least two vertices, a vertex is called external if it is not a cut vertex. In a tree, an external vertex is exactly a pendant vertex. Let ϵ (G) be the number of external vertices in G. In this paper, we prove that m (G , λ) ≤ ϵ (G) − 1 for any λ and characterize the extremal graphs with m (G , − 1) = ϵ (G) − 1 , which generalizes the main result of Wang et al. [Linear Multi. Alg., 2020] from a tree to an arbitrary connected graph. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the minimum number of triangles, denoted by t(n,k) $t(n,k)$, in n $n$‐vertex k $k$‐regular graphs, where n $n$ is an odd integer and k $k$ is an even integer. The well‐known Andrásfai–Erdős–Sós Theorem has established that t(n,k)>0 $t(n,k)\gt 0$ if k>2n5 $k\gt \frac{2n}{5}$. In a striking work, Lo has provided the exact value of t(n,k) $t(n,k)$ for sufficiently large n $n$, given that 2n5+12n5

We present a renormalization group (RG) analysis of the problem of Anderson localization on a random regular graph (RRG) which generalizes the RG of Abrahams, Anderson, Licciardello, and Ramakrishnan to infinite-dimensional graphs. The RG equations necessarily involve two parameters (one being the changing connectivity of subtrees), but we show that the one-parameter scaling hypothesis is recovered for sufficiently large system sizes for both eigenstates and spectrum observables. We also explain the nonmonotonic behavior of dynamical and spectral quantities as a function of the system size for values of disorder close to the transition, by identifying two terms in the beta function of the running fractal dimension of different signs and functional dependence. Our theory provides a simple and coherent explanation for the unusual scaling behavior observed in numerical data of the Anderson model on RRG and of many-body localization. [ABSTRACT FROM AUTHOR]

We introduce the notion of q -analogs of strongly regular graphs and give several examples of such structures. We prove a necessary condition on the parameters, show the connection to designs over finite fields, and present a classification. [ABSTRACT FROM AUTHOR]

In this paper, we primarily focus on the eigenvalues of the adjacency matrix and Seidel matrix of chain graphs, referred to as eigenvalues and Seidel eigenvalues of these graphs, respectively. Firstly, we utilize the characteristic polynomial of the adjacency matrix of a chain graph to construct infinite pairs of non-isomorphic cospectral chain graphs. Next, we determine the inertia of the Seidel matrix of a chain graph and establish an interval that does not contain the Seidel eigenvalues of chain graphs. Lastly, we characterize chain graphs with distinct Seidel eigenvalues. [ABSTRACT FROM AUTHOR]

Let L be a nonnegative integer and ΓL the power set of the set {0, 1,…,L}. Then there is an adjacency relation in ΓL such that ΓL together with the relation forms a regular graph. In this paper, we propose a model of continuous-time magnetic quantum walk (MQW) on the graph ΓL, and investigate its properties from a viewpoint of probability and quantum information. We first introduce a magnetic Laplacian ΔL(휃) on the graph ΓL and examine its spectrum. And then, with ΔL(휃) as the Hamiltonian, we construct our model of continuous-time MQW on the graph ΓL. We find that the model has probability distributions that are completely independent of the magnetic potential at all times. And we show that it has perfect state transfer at time t = π 2 when the magnetic potential satisfies some mild conditions. Some other interesting results are also obtained. [ABSTRACT FROM AUTHOR]

For a simple graph G on n vertices the Seidel Estrada index of G, denoted by $ SEE(G) $ SEE (G) , is defined as $ SEE(G)=\sum _{i=1}^ne^{\theta _i} $ SEE (G) = ∑ i = 1 n e θ i , where $ \theta _1,\ldots,\theta _n $ θ 1 , ... , θ n are the Seidel eigenvalues (the eigenvalues of the Seidel matrix) of G. In this paper, we find the maximum and minimum values of the Seidel Estrada index among all graphs with the fixed number of vertices. Our results confirm some conjectures on Seidel Estrada index of graphs that have been posed in [M. Hakimi-Nezhaad, M. Ghorbani, On the Estrada Index of Seidel Matrix, Mathematics Interdisciplinary Research5 (2020) 43–54]. [ABSTRACT FROM AUTHOR]

Aldous and Fill (2002) conjectured that the maximum relaxation time for the random walk on a connected regular graph with n vertices is (1 + o (1)) 3 n 2 2 π 2 . A conjecture by Guiduli and Mohar (1996) predicts the structure of graphs whose algebraic connectivity μ is the smallest among all connected graphs whose minimum degree δ is a given d. We prove that this conjecture implies the Aldous–Fill conjecture for odd d. We pose another conjecture on the structure of d -regular graphs with minimum μ , and show that this also implies the Aldous–Fill conjecture for even d. In the literature, it has been noted empirically that graphs with small μ tend to have a large diameter. In this regard, Guiduli (1996) asked if the cubic graphs with maximum diameter have algebraic connectivity smaller than all others. Motivated by these, we investigate the interplay between the graphs with maximum diameter and those with minimum algebraic connectivity. We show that the answer to Guiduli problem in its general form, that is for d -regular graphs for every d ≥ 3 is negative. We aim to develop an asymptotic formulation of the problem. It is proven that d -regular graphs for d ≥ 5 as well as graphs with δ = d for d ≥ 4 with asymptotically maximum diameter, do not necessarily exhibit the asymptotically smallest μ. We conjecture that d -regular graphs (or graphs with δ = d) that have asymptotically smallest μ , should have asymptotically maximum diameter. The above results rely heavily on our understanding of the structure as well as optimal estimation of the algebraic connectivity of nearly maximum-diameter graphs, from which the Aldous–Fill conjecture for this family of graphs also follows. [ABSTRACT FROM AUTHOR]

The graph a K m , m ∇ C n is named the generalized double-wheel graph. A graph G is said to be M-integral (resp. A-integral, D-integral, D L -integral or D Q -integral) if all eigenvalues of its matrix M (resp. adjacency matrix A(G) , distance matrix D(G) , distance Laplacian matrix D L (G) or distance signless Laplacian matrix D Q (G) ) are integers. In this paper, we completely determine all D-integral, D L -integral and D Q -integral generalized double-wheel graphs respectively. [ABSTRACT FROM AUTHOR]

A graph G whose vertex set can be partitioned into a total dominating set and an independent dominating set is called a TI-graph. We give constructions that yield infinite families of graphs that are TI-graphs, as well as constructions that yield infinite families of graphs that are not TI-graphs. We study regular graphs that are TI-graphs. Among other results, we prove that all toroidal graphs are TI-graphs. [ABSTRACT FROM AUTHOR]

In this paper, the unique graph with the minimal second smallest normalized Laplacian eigenvalue of unicyclic graphs with fixed girth is determined. [ABSTRACT FROM AUTHOR]

A given graph H is called realizable by a graph G if G [ N (v) ] ≅ H for every vertex v of G. The Trahtenbrot–Zykov problem says that which graphs are realizable. We consider a problem somewhat opposite in a more general setting. Let t be a positive integer. We characterize all graphs G such that G - N [ v ] ∈ F for every vertex v of G, where F is the set of all t-regular graphs. Indeed, for 1 ≤ t ≤ 3 , the graphs are characterized by the same authors recently. Let t ≥ 4 . In this paper, we prove that there is no graph G such that G - N [ u ] ∈ F for each vertex u ∈ V (G) if G - N [ v ] ≅ H ∈ F for some vertex v ∈ V (G) and d i a m (H) ≥ 4 . In addition, we characterize all graphs G such that G - N [ v ] ≅ H for each v ∈ V (G) if H is one of two special graphs whose diameter are 2 and 3, respectively. [ABSTRACT FROM AUTHOR]

Codebooks with small inner-product correlations are desirable in many fields, including compressed sensing, direct spread code division multiple access (CDMA) systems, and space-time codes. The objective of this paper is to present a class of codebooks and explore their applications in strongly regular Cayley graphs. The obtained codebooks are nearly optimal in the sense that their maximum cross-correlation amplitude nearly meets the Welch bound. As far as we know, this construction of codebooks provides new parameters. [ABSTRACT FROM AUTHOR]

We introduce two new methods for approximating the all‐terminal reliability of undirected graphs. First, we introduce an edge removal process: remove edges at random, one at a time, until the graph becomes disconnected. We show that the expected number of edges thus removed is equal to (m+1)A$$ \left(m+1\right)A $$, where m$$ m $$ is the number of edges in the graph, and A$$ A $$ is the average of the all‐terminal reliability polynomial. Based on this process, we propose a Monte‐Carlo algorithm to quickly estimate the graph reliability (whose exact computation is NP‐hard). Moreover, we show that the distribution of the edge removal process can be used to quickly approximate the reliability polynomial. We then propose increasingly accurate asymptotics for graph reliability based solely on degree distributions of the graph. These asymptotics are tested against several real‐world networks and are shown to be accurate for sufficiently dense graphs. While the approach starts to fail for "subway‐like" networks that contain many paths of vertices of degree two, different asymptotics are derived for such networks. [ABSTRACT FROM AUTHOR]

Fractional repetition codes (FRCs) are a special family of storage codes with the repair-by-transfer property in distributed storage systems. Constructions of FRCs are naturally related to combinatorial designs, graphs, and hypergraphs. In this paper, we consider an extremal problem on regular graphs related to FRCs where each packet is stored on ρ = 2 nodes. The problem asks for the minimum number of vertices in an α -regular graph such that any k vertices induce at most δ edges, where α , k, and δ are given. Such a problem is closely related to (and can be seen as a generalization of) the classical cage problem, and its solution indicates the minimum number of nodes in an FRC-based distributed storage system. In addition, we further consider FRCs with ρ ≥ 3 and generalize the extremal problem to a linear hypergraph version. [ABSTRACT FROM AUTHOR]

Let G$$ G $$ be a d$$ d $$‐regular graph on n$$ n $$ vertices. Frieze, Gould, Karoński, and Pfender began the study of the following random spanning subgraph model H=H(G)$$ H=H(G) $$. Assign independently to each vertex v$$ v $$ of G$$ G $$ a uniform random number x(v)∈[0,1]$$ x(v)\in \left[0,1\right] $$, and an edge (u,v)$$ \left(u,v\right) $$ of G$$ G $$ is an edge of H$$ H $$ if and only if x(u)+x(v)≥1$$ x(u)+x(v)\ge 1 $$. Addressing a problem of Alon and Wei, we prove that if d=o(n/(logn)12)$$ d=o\left(n/{\left(\log n\right)}^{12}\right) $$, then with high probability, for each nonnegative integer k≤d$$ k\le d $$, there are (1+o(1))n/(d+1)$$ \left(1+o(1)\right)n/\left(d+1\right) $$ vertices of degree k$$ k $$ in H$$ H $$. [ABSTRACT FROM AUTHOR]

Partial cubes are graphs that can be isometrically embedded into hypercubes. Convex cycles play an important role in the study of partial cubes. In this paper, we prove that a regular partial cube is a hypercube (resp., a Doubled Odd graph, an even cycle of length 2n $2n$ where n⩾4 $n\geqslant 4$) if and only if all its convex cycles are 4‐cycles (resp., 6‐cycles, 2n $2n$‐cycles). In particular, the partial cubes whose all convex cycles are 4‐cycles are equivalent to almost‐median graphs. Therefore, we conclude that regular almost‐median graphs are exactly hypercubes, which generalizes the result by Mulder—regular median graphs are hypercubes. [ABSTRACT FROM AUTHOR]

This paper lies in the context of the studies of eigenfunctions of graphs having minimum cardinality of support. One of the tools is the weight‐distribution bound, a lower bound on the cardinality of support of an eigenfunction of a distance‐regular graph corresponding to a nonprincipal eigenvalue. The tightness of the weight‐distribution bound was previously shown in general for the smallest eigenvalue of a Grassmann graph. However, a characterisation of optimal eigenfunctions was not obtained. Motivated by this open problem, we consider the class of strongly regular Grassmann graphs and give the required characterisation in this case. We then show the tightness of the weight‐distribution bound for block graphs of affine designs (defined on the lines of an affine space with two lines being adjacent when intersect) and obtain a similar characterisation of optimal eigenfunctions. [ABSTRACT FROM AUTHOR]

We derive attainable upper bounds on the algebraic connectivity (spectral gap) of a regular graph in terms of its diameter and girth. This bound agrees with the well‐known Alon–Boppana–Friedman bound for graphs of even diameter, but is an improvement for graphs of odd diameter. For the girth bound, we show that only Moore graphs can attain it, and these only exist for well‐known special cases. For the diameter bound, we use a combination of stochastic algorithms and exhaustive search to find graphs which attain it. For 3‐regular graphs, we find attainable graphs for all diameters D $D$ up to and including D=9 $D=9$ (the case of D=10 $D=10$ is open). These graphs are extremely rare and also have high girth; for example, we found exactly 45 distinct cubic graphs on 44 vertices attaining the upper bound when D=7 $D=7$; all have girth 8. We also exhibit several infinite families attaining the upper bound with respect to diameter or girth. In particular, when d $d$ is a power of prime, we construct a d $d$‐regular graph having diameter 4 and girth 6 which attains the upper bound with respect to diameter. [ABSTRACT FROM AUTHOR]

Multiplayer games on graphs are at the heart of theoretical descriptions of key evolutionary processes that govern vital social and natural systems. However, a comprehensive theoretical framework for solving multiplayer games with an arbitrary number of strategies on graphs is still missing. Here, we solve this by drawing an analogy with the Balls-and-Boxes problem, based on which we show that the local configuration of multiplayer games on graphs is equivalent to distributing k identical co-players among n distinct strategies. We use this to derive the replicator equation for any n-strategy multiplayer game under weak selection, which can be solved in polynomial time. As an example, we revisit the second-order free-riding problem, where costly punishment cannot truly resolve social dilemmas in a well-mixed population. Yet, in structured populations, we derive an accurate threshold for the punishment strength, beyond which punishment can either lead to the extinction of defection or transform the system into a rock-paper-scissors-like cycle. The analytical solution also qualitatively agrees with the phase diagrams that were previously obtained for non-marginal selection strengths. Our framework thus allows an exploration of any multi-strategy multiplayer game on regular graphs. Evolutionary multiplayer games in structured populations illustrate a variety of phenomena in natural and social systems. This research provides a mathematical framework to analyze multiplayer games with an arbitrary number of strategies on regular graphs. [ABSTRACT FROM AUTHOR]

We study Markov population processes on large graphs, with the local state transition rates of a single vertex being a linear function of its neighborhood. A simple way to approximate such processes is by a system of ODEs called the homogeneous mean-field approximation (HMFA). Our main result is showing that HMFA is guaranteed to be the large graph limit of the stochastic dynamics on a finite time horizon if and only if the graph-sequence is quasi-random. An explicit error bound is given and it is 1 N plus the largest discrepancy of the graph. For Erdős–Rényi and random regular graphs we show an error bound of order the inverse square root of the average degree. In general, diverging average degrees is shown to be a necessary condition for the HMFA to be accurate. Under special conditions, some of these results also apply to more detailed type of approximations like the inhomogenous mean field approximation (IHMFA). We pay special attention to epidemic applications such as the SIS process. [ABSTRACT FROM AUTHOR]

Linear codes are the most important family of codes in cryptography and coding theory. Some codes only have a few weights and are widely used in many areas, such as authentication codes, secret sharing schemes and strongly regular graphs. By setting p ≡ 1 (mod 4) , we constructed an infinite family of linear codes using two distinct weakly regular unbalanced (and balanced) plateaued functions with index (p − 1) / 2 . Their weight distributions were completely determined by applying exponential sums and Walsh transform. As a result, most of our constructed codes have a few nonzero weights and are minimal. [ABSTRACT FROM AUTHOR]

A common choice for the evolution of the knotted graphs in loop quantum gravity is to use the Pachner moves, adapted to graphs from their dual triangulations. Here, we show that the natural way to consistently use these moves is on framed graphs with edge twists, where the Pachner moves can only be performed when the twists, and the vertices the edges are incident on, meet certain criteria. For other twists, one can introduce an algebraic object, which allow any knotted graph with framed edges to be written in terms of a generalized braid group. [ABSTRACT FROM AUTHOR]

There is a non-unital ring I of order 4 defined by generators and relations as I = 〈 a , b | 2 a = 2 b = 0 , a 2 = b , a b = 0 〉. In this paper, we present special constructions of linear codes over I from the adjacency matrices of two class association schemes. These consist of either Strongly Regular Graphs (SRGs) or Doubly Regular Tournaments (DRTs). We investigate the conditions under which these codes are self-orthogonal, quasi self-dual, or Type IV. As a byproduct of this study, some diophantine relations on the weight of sum of vectors with coefficients in I are derived. Some examples of codes with minimum distance better than that of Type IV codes over unital rings of the same order in modest lengths are given. [ABSTRACT FROM AUTHOR]

Using an approach from finite group representation theory we construct quaternary non-projective codes with parameters [ 6 9 3 , 6 , 4 8 0 ] 4 , [ 1 3 8 6 , 6 , 1 0 0 8 ] 4 , [ 2 0 1 6 , 6 , 1 4 8 8 ] 4 , quaternary projective codes with parameters [ 2 3 1 , 6 , 1 6 0 ] 4 , [ 4 6 2 , 6 , 3 3 6 ] 4 and [ 6 7 2 , 6 , 4 9 6 ] 4 and binary projective codes with parameters [ 6 9 3 , 1 2 , 3 2 0 ] 2 , [ 1 3 8 6 , 1 2 , 6 7 2 ] 2 , [ 2 0 1 6 , 1 2 , 9 9 2 ] 2 as examples of two-weight codes on which a finite almost quasisimple group of sporadic type acts transitively as permutation groups of automorphisms. In particular, we show that these codes are invariant under the 3 -fold covers 3 ̂ M 2 2 and 3 ̂ M 2 2 : 2 , respectively, of the Mathieu groups M 2 2 and M 2 2 : 2. Employing a known construction of strongly regular graphs from projective two-weight codes we obtain from the binary projective (respectively, quaternary projective) two-weight codes with parameters those given above, the strongly regular graphs with parameters (4 0 9 6 , 6 9 3 , 1 5 2 , 1 1 0) , (4 0 9 6 , 1 3 8 6 , 4 8 2 , 4 6 2) , and (4 0 9 6 , 2 0 1 6 , 9 9 2 , 9 9 2) , respectively. The latter graph can be viewed as a 2 - (4 0 9 6 , 2 0 1 6 , 9 9 2) -symmetric design with the symmetric difference property whose residual and derived designs with respect to a block give rise to binary self-complementary codes meeting the Grey–Rankin bound with equality. [ABSTRACT FROM AUTHOR]

A simple undirected regular graph is said to be semisymmetric if it is edge-transitive but not vertex-transitive. For a semisymmetric graph Γ of order 2 p 3 , p a prime, it is well known that Γ is bipartite with two biparts having equal size. The complete classification of such graphs has been given for the full automorphism group Aut (Γ) acting unfaithfully on at least one bipart of Γ , which shows that there is only one infinite family of such graphs with valency p 2. The graphs of this kind have been determined when Aut (Γ) acts faithfully and primitively on at least one bipart of Γ , and thus there is only one remaining case for classifying such graphs of valency p 2 , Aut (Γ) acting faithfully and imprimitively on both biparts of Γ , which is dealt with in this paper. As a result, there is only one infinite family of semisymmetric graphs of order 2 p 3 with valency p 2. [ABSTRACT FROM AUTHOR]

For positive integers $ m_{1},m_{2},\ldots,m_{h} $ m 1 , m 2 , ... , m h , a generalized balanced tree $ T(m_{1},m_{2},\ldots,m_{h}) $ T (m 1 , m 2 , ... , m h) is a rooted tree of height h such that every vertex of depth i has $ m_{i+1} $ m i + 1 children, $ 0\leq i\leq ~h-1 $ 0 ≤ i ≤ h − 1. The distance matrix $ D(G) $ D (G) of a simple connected graph G of order n is an $ n \times n $ n × n matrix whose $ (i,j){{\rm th}} $ (i , j) th entry is the distance between $ i{{\rm th}} $ i th and $ j{{\rm th}} $ j th vertices. A connected graph G is called a k-partitioned transmission regular graph if there exists a vertex partition $ \{V_{1},V_{2},\ldots,V_{k}\} $ { V 1 , V 2 , ... , V k } of G so that for $ 1\leq i,j \leq k $ 1 ≤ i , j ≤ k , and $ x\in V_{i} $ x ∈ V i , $ \sum _{y\in V_{j}} d(x,y) $ ∑ y ∈ V j d (x , y) is a constant. Here we show that $ T(m_{1},m_{2},\ldots,m_{h}) $ T (m 1 , m 2 , ... , m h) is an $ (h+1) $ (h + 1) -partitioned transmission regular graph. We find an $ (h+1)\times (h+1) $ (h + 1) × (h + 1) matrix whose largest eigenvalue is the distance spectral radius of $ T(m_{1},m_{2},\ldots,m_{h}) $ T (m 1 , m 2 , ... , m h). We obtain the characteristic polynomial of $ D(T(m_{1},m_{2},\ldots,m_{h})) $ D (T (m 1 , m 2 , ... , m h)) in terms of that of the smaller matrices and give an idea to find the full spectrum. Moreover, we get that $ D(T(m_{1},m_{2},\ldots,m_{h})) $ D (T (m 1 , m 2 , ... , m h)) has $ -2 $ − 2 an eigenvalue with multiplicity at least $ m_{1}\cdots m_{h-1} (m_{h}-1) $ m 1 ⋯ m h − 1 (m h − 1) and $ -(m_{h}+2)\pm \sqrt {m_{h}(m_{h}+4)} $ − (m h + 2) ± m h (m h + 4) as eigenvalues with multiplicity at least $ m_{1}\cdots m_{h-2} (m_{h-1}-1) $ m 1 ⋯ m h − 2 (m h − 1 − 1). [ABSTRACT FROM AUTHOR]

A simple graph is called semisymmetric if it is regular and edge-transitive but not vertex-transitive. Let p be an arbitrary prime. Folkman [J. Folkman, Regular line-symmetric graphs, J. Combinatorial Theory, 3 (1967) 215-232.] proved that there are no cubic semisymmetric graphs of order 2p or 2p². In this paper, an extension of his result in the case of cubic graphs of order 44p or 44p² is given. By using group theoretic methods, we prove that there are no connected cubic semisymmetric graphs of order 44p or 44p². [ABSTRACT FROM AUTHOR]

The distance matrix, distance eigenvalue, and distance energy of a connected graph have been studied in detail in literature where as the study on distance seidel matrix associated with a connected graph is in progress. The eigenvalues... of the distance seidel matrix DS(G) of a graph G forms the distance seidel spectrum of G. We describe here the distance seidel spectrum of some types of subdivision related graphs of a regular graph in terms of its adjacency spectrum. We also derive analytic expressions for the distance seidel energy of (Cp), the partial complement of the subdivision graph of a cycle Cp and the distance seidel energy of S(Cp), the complement of the even cycle C2p. [ABSTRACT FROM AUTHOR]

This paper delves into three research directions, leveraging the Lovász ϑ-function of a graph. First, it focuses on the Shannon capacity of graphs, providing new results that determine the capacity for two infinite subclasses of strongly regular graphs, and extending prior results. The second part explores cospectral and nonisomorphic graphs, drawing on a work by Berman and Hamud (2024), and it derives related properties of two types of joins of graphs. For every even integer such that n≥14, it is constructively proven that there exist connected, irregular, cospectral, and nonisomorphic graphs on n vertices, being jointly cospectral with respect to their adjacency, Laplacian, signless Laplacian, and normalized Laplacian matrices, while also sharing identical independence, clique, and chromatic numbers, but being distinguished by their Lovász ϑ-functions. The third part focuses on establishing bounds on graph invariants, particularly emphasizing strongly regular graphs and triangle-free graphs, and compares the tightness of these bounds to existing ones. The paper derives spectral upper and lower bounds on the vector and strict vector chromatic numbers of regular graphs, providing sufficient conditions for the attainability of these bounds. Exact closed-form expressions for the vector and strict vector chromatic numbers are derived for all strongly regular graphs and for all graphs that are vertex- and edge-transitive, demonstrating that these two types of chromatic numbers coincide for every such graph. This work resolves a query regarding the variant of the ϑ-function by Schrijver and the identical function by McEliece et al. (1978). It shows, by a counterexample, that the ϑ-function variant by Schrijver does not possess the property of the Lovász ϑ-function of forming an upper bound on the Shannon capacity of a graph. This research paper also serves as a tutorial of mutual interest in zero-error information theory and algebraic graph theory. [ABSTRACT FROM AUTHOR]

Inspired by Sheehan's conjecture that no 4-regular graph contains exactly one hamiltonian cycle, we prove results on hamiltonian cycles in regular graphs and nearly regular graphs. We fully disprove a conjecture of Haythorpe on the minimum number of hamiltonian cycles in regular hamiltonian graphs, thereby extending a result of Zamfirescu, as well as correct and complement Haythorpe's computational enumerative results from [Exp. Math. 27 (2018), no. 4, 426–430]. Thereafter, we use the Lovász Local Lemma to extend Thomassen's independent dominating set method. This extension allows us to find a second hamiltonian cycle that inherits linearly many edges from the first hamiltonian cycle. Regarding the limitations of this method, we answer a question of Haxell, Seamone, and Verstraete, and settle the first open case of a problem of Thomassen by showing that for k \in \{5, 6\} there exist infinitely many k-regular hamiltonian graphs having no independent dominating set with respect to a prescribed hamiltonian cycle. Motivated by an observation of Aldred and Thomassen, we prove that for every \kappa \in \{ 2, 3 \} and any positive integer k, there are infinitely many non-regular graphs of connectivity \kappa containing exactly one hamiltonian cycle and in which every vertex has degree 3 or 2k. [ABSTRACT FROM AUTHOR]

Let G be a graph and F be a connected subgraph of G except for K 1. Let F = { F 1 , F 2 , ... , F k } be a set of subgraphs of G such that each member of F is isomorphic to F. The F -(disjoint)-structure edge-connectivity is the minimum cardinality of F such that E (F) 's removal will disconnect G. If every member of F is isomorphic to a connected subgraph of F , then F -(disjoint)-substructure edge-connectivity is defined similarly. In this paper, we determine the star-(disjoint)-substructure edge-connectivity and star-structure edge-connectivity of an n -regular graph G , and give an upper bound on the star-disjoint-structure edge-connectivity of an n -regular graph G. We derive the F -(disjoint)-substructure edge-connectivity of hypercube-like graphs H L n and Cayley graphs generated by transposition trees Γ n (except for star graphs S n) for F being C 4 and P 4 , and show a lower bound on the F -(disjoint)-structure edge-connectivity of H L n and Γ n (except for S n) for F being C 4 and P 4. As applications, we determine the F -(disjoint)-structure edge-connectivity of crossed cubes C Q n and bubble-sort graphs B n for F being C 4 and P 4 , respectively. Furthermore, we obtain the F -(disjoint)-(sub)structure edge-connectivity of S n for F being C 6 and P 6. [ABSTRACT FROM AUTHOR]

The augmented Zagreb index (A Z I) of a graph G is the sum of the weights d (u) d (v) / (d (u) + d (v) − 2) 3 over all edges u v of G , where d (u) is the degree of the vertex u in G. Let U n g be the set of all unicyclic graphs on n vertices with girth g. In this paper, we prove that if G is a graph with the maximum A Z I in U n g , such that n ≥ 3 2 (g − 2) + 451 and g ≥ 4 , then G is a sunlet graph, i.e. G is a unicyclic graph such that removing all leaves gives a cycle. Furthermore, we have proven that G is always a g o o d sunlet graph, in which all leaves are adjacent to the vertices in the cycle in a regular pattern. Finally we propose a new tool that could help to characterize the graph with the maximum A Z I in U n g. [ABSTRACT FROM AUTHOR]

We study how few longest cycles a regular graph can have under additional constraints. For each integer r ≥ 5 , we give exponential improvements for the best asymptotic upper bounds for this invariant under the additional constraint that the graphs are r -regular hamiltonian graphs. Earlier work showed that a conjecture by Haythorpe (2018) on a lower bound for this invariant is false because of an incorrect constant factor, whereas our results imply that the conjecture is even asymptotically incorrect. Motivated by a question of Zamfirescu (2022) and work of Chia and Thomassen (2012), we also study this invariant for non-hamiltonian 2-connected r -regular graphs and show that in this case the invariant can be bounded from above by a constant for all large enough graphs, even for graphs with arbitrarily large girth. [ABSTRACT FROM AUTHOR]

We study solutions of a quadratic matrix equation arising in Riemannian geometry. Let S be a real symmetric n × n -matrix with zeros on the diagonal and let θ be a real number. We construct nonzero solutions (S , θ) of the set of quadratic equations ∑ k S i , k = 0 and ∑ k S i , k S k , j + S i , j 2 = θ S i , j for i < j. Our solutions relate the equations to strongly regular graphs, to group rings, and to multiplicative characters of finite fields. [ABSTRACT FROM AUTHOR]

"Which graphs are determined by their spectra (DS for short)?" is an important and challenging topic in spectral graph theory. Let G be an n -vertex graph with adjacency matrix A (G) and adjacency walk matrix W A (G) = [ e , A (G) e , ... , A n − 1 (G) e ]. We call G controllable if the rank of W A (G) is n over R and noncontrollable otherwise. In Wang (2017), the author gave a simple condition for a controllable graph to be determined by their generalized adjacency spectrum (DGAS for short). However, the result fails for noncontrollable graphs. In this paper, we consider the problem in the context of the generalized distance spectrum. Let G be a connected graph with distance matrix D. A graph G is determined by its generalized distance spectrum (DG D S for short) if any graph H sharing the same generalized distance spectrum with G must be isomorphic to G. The paper aims to extend the result in Wang (2017) from generalized adjacency spectrum to generalized distance spectrum. Besides, a simple arithmetic criterion is given to determine whether a connected graph is DG D S or not, which is applicable to some kind of noncontrollable graphs, e.g., regular graphs. [ABSTRACT FROM AUTHOR]

A graph G = (V G , E G) is said to be a cograph if the path P 4 does not appear among its induced subgraphs. The vicinal preorder ≺ on the vertex set V G is defined in terms of inclusions between neighborhoods. The minimum number ∇ (G) of ≺-chains required to cover G is called the Dilworth number of G. In this paper it is proved that for a cograph G , the multiplicity of every Seidel eigenvalue λ ≠ ± 1 does not exceed ∇ (G). This bound turns out to be tight and can be further improved for threshold graphs. Moreover, it is shown that cographs with at least two vertices have no Seidel eigenvalues in the interval (− 1 , 1). [ABSTRACT FROM AUTHOR]

In this article, we construct (graded) automorphisms fixing all vertices of Leavitt path algebras of arbitrary graphs in terms of general linear groups over corners of these algebras. As an application, we study Zhang twist of Leavitt path algebras and describe new classes of irreducible representations of Leavitt path algebras of rose graphs R n with n petals. [ABSTRACT FROM AUTHOR]

Every k-regular graph has a fractional perfect matching via assigning each edge a fractional number 1 k . How many edges are deleted from a regular graph so that the resulting graph still has a fractional perfect matching? Let G be a k-regular graph with n vertices. In this paper, we prove that the fractional matching number of the resulting graph deleting any (t + 1) k - 1 2 edges from G is not less than 1 2 (n - t) . In particular, taking t = 0 , we deduce that the resulting graph deleting any ⌊ k - 1 2 ⌋ edges from G has a fractional perfect matching. Specially, we can delete any k - 1 edges from G other than exceptions such that the resulting graph has a fractional perfect matching when n ≤ 2 k - 2 . Further, the resulting graph deleting any k + l - 1 2 edges from a k-regular l-edge-connected graph with an even number of vertices has a fractional perfect matching. As applications, some values or bounds on the fractional matching preclusion number of regular graphs are deduced immediately. [ABSTRACT FROM AUTHOR]

A tree T $T$ is said to be even if all pairs of vertices of degree one in T $T$ are joined by a path of even length. We conjecture that every r $r$‐regular nonbipartite connected graph G $G$ has a spanning even tree and verify this conjecture when G $G$ has a 2‐factor. Well‐known results of Petersen and Hanson et al. imply that the only remaining unsolved case is when r $r$ is odd and G $G$ has at least r $r$ bridges. We investigate this case further and propose some related conjectures. [ABSTRACT FROM AUTHOR]

Deza digraphs were introduced in 2003 by Zhang and Wang as directed graph version of Deza graphs, that also generalize the notion of directed strongly regular graphs. In this paper, we give several new constructions of Deza digraphs. Further, we introduce twin and Siamese twin (directed) Deza graphs and construct several examples. Finally, we study a variation of directed Deza graphs and provide a construction from finite fields. [ABSTRACT FROM AUTHOR]

A dominating broadcast of a graph G is a function f : V (G) → { 0 , 1 , 2 , ... , diam (G) } such that f (v) ⩽ e (v) for all v ∈ V (G) , where e (v) is the eccentricity of v , and for every u ∈ V (G) , there exists a vertex v with f (v) ⩾ 1 and d (u , v) ⩽ f (v). The cost of f is ∑ v ∈ V (G) f (v). The minimum cost over all the dominating broadcasts of G is called the broadcast domination number γ b (G) of G. In this paper, we give new upper and lower bounds for γ b (G). We show that both the bounds are tight. Also, we improve the upper bound for a subclass of regular graphs. Further, we explore the broadcast domination numbers of generalized Petersen graphs and a subclass of circulant graphs. [ABSTRACT FROM AUTHOR]