Spectral radius of strongly connected digraphs

Let $D$ be a digraph with vertex set $V\left(D\right)$ and $A$ be the adjacency matrix of $D$. The largest eigenvalue of $A$, denoted by $\rho \left(D\right)$, is called the spectral radius of the digraph $D$. In this paper, we establish some sharp upper or lower bounds for digraphs with some given graph parameters, such as clique number, girth, and vertex connectivity, and characterize the corresponding extremal graphs. In addition, we give the exact value of the spectral radii of those digraphs.     

Edge proximity and matching extension in punctured planar triangulations

A matching $M$ in a graph $G$ is said to be extendable if there exists a perfect matching of $G$ containing $M$. In 1989, it was shown that every connected planar graph with at least $8$ vertices has a matching of size three which is not extendable. In contrast, the study of extending certain matchings of size three or more has made progress in the past decade when the given graph is $5$-connected planar triangulation or $5$-connected plane graphs with few non-triangular faces.In this paper, we prove that if $G$ is a $5$-connected plane graph of even order in which at most two faces are not triangular and $M$ is a matching of size four in which the edges lie pairwise distance at least three apart, then $M$ is extendable. A related result concerning perfect matching with proscribed edges is shown as well.     

Deformation cohomology of Lie algebroids and Morita equivalence

Let $A?M$ be a Lie algebroid. In this short note, we prove that a pull-back of A along a fibration with homologically m-connected fibers shares the same deformation cohomology of A up to degree m.     

A1-homotopy groups,excision, and solvable quotients

We study some properties of ${\mathbb{A}}^1$-homotopy groups: geometric interpretations of connectivity, excision results, and a re-interpretation of quotients by free actions of connected solvable groups in terms of covering spaces in the sense of ${\mathbb{A}}^1$-homotopy theory. These concepts and results are well suited to the study of certain quotients via geometric invariant theory. As a case study in the geometry of solvable group quotients, we investigate ${\mathbb{A}}^1$-homotopy groups of smooth toric varieties. We give simple combinatorial conditions (in terms of fans) guaranteeing vanishing of low degree ${\mathbb{A}}^1$-homotopy groups of smooth (proper) toric varieties. Finally, in certain cases, we can actually compute the “next” non-vanishing ${\mathbb{A}}^1$-homotopy group (beyond ${\pi }_1^{{\mathbb{A}}^1}$) of a smooth toric variety. From this point of view, ${\mathbb{A}}^1$-homotopy theory, even with its exquisite sensitivity to algebro-geometric structure, is almost “as tractable” (in low degrees) as ordinary homotopy for large classes of interesting varieties.     

New characterizations of Gallai’s i-triangulated graphs

The i-triangulated graphs, introduced by Tibor Gallai in the early 1960s, have a number of characterizations—one of the simplest is that every odd cycle of length $5$ or more has noncrossing chords. A variety of new characterizations are proved, starting with a simple forbidden induced subgraph characterization and including the following two:(1) Every 2-connected induced subgraph $H$ is bipartite or chordal or, for every induced even cycle $C$ of $H$, the intersection of the neighborhoods in $H$ of all the vertices of $C$ induces a complete multipartite subgraph.(2) For every 2-connected induced subgraph $H$ that is not bipartite, every cardinality-2 minimal vertex separator of $H$ induces an edge.     

Degree-equipartite graphs

A graph $G$ of order $2n$ is called degree-equipartite if for every $n$-element set $A?V\left(G\right)$, the degree sequences of the induced subgraphs $G\left[A\right]$ and $G[V\left(G\right)?A]$ are the same. In this paper, we characterize all degree-equipartite graphs. This answers Problem 1 in the paper by Grünbaum et al. [B. Grünbaum, T. Kaiser, D. Král, and M. Rosenfeld, Equipartite graphs, Israel J. Math. 168 (2008) 431–444].     

The fixation probability and time for a doubly beneficial mutant

For a highly beneficial mutant $A$ entering a randomly reproducing population of constant size, we study the situation when a second beneficial mutant $B$ arises before $A$ has fixed. If the selection coefficient of $B$ is greater than the selection coefficient of $A$, and if $A$ and $B$ can recombine at some rate $\rho$, there is a chance that the double beneficial mutant $AB$ forms and eventually fixes. We give a convergence result for the fixation probability of $AB$ and its fixation time for large selection coefficients.     

Spectral radius of power graphs on certain finite groups

The power graph of a group $G$ is a graph with vertex set $G$ and two distinct vertices are adjacent if and only if one is an integral power of the other. In this paper we find both upper and lower bounds for the spectral radius of power graph of cyclic group $C_n$ and characterize the graphs for which these bounds are extremal. Further we compute spectra of power graphs of dihedral group $D_{2n}$ and dicyclic group $Q_{4n}$ partially and give bounds for the spectral radii of these graphs.     

On the radius and the attachment number of tetravalent half-arc-transitive graphs

In this paper, we study the relationship between the radius $r$ and the attachment number $a$ of a tetravalent graph admitting a half-arc-transitive group of automorphisms. These two parameters were first introduced in Maru?i? (1998), where among other things it was proved that $a$ always divides $2r$. Intrigued by the empirical data from the census (Poto?nik et al., 2015) of all such graphs of order up to 1000 we pose the question of whether all examples for which $a$ does not divide $r$ are arc-transitive. We prove that the answer to this question is positive in the case when $a$ is twice an odd number. In addition, we completely characterise the tetravalent graphs admitting a half-arc-transitive group with $r=3$ and $a=2$, and prove that they arise as non-sectional split $2$-fold covers of line graphs of $2$-arc-transitive cubic graphs.     

Max-cut and extendability of matchings in distance-regular graphs

A connected graph $G$ of even order $v$ is called $t$-extendable if it contains a perfect matching, $t<v/2$ and any matching of $t$ edges is contained in some perfect matching. The extendability of $G$ is the maximum $t$ such that $G$ is $t$-extendable. Since its introduction by Plummer in the 1980s, this combinatorial parameter has been studied for many classes of interesting graphs. In 2005, Brouwer and Haemers proved that every distance-regular graph of even order is $1$-extendable and in 2014, Cioabă and Li showed that any connected strongly regular graph of even order is 3-extendable except for a small number of exceptions.In this paper, we extend and generalize these results. We prove that all distance-regular graphs with diameter $D\ge 3$ are 2-extendable and we also obtain several better lower bounds for the extendability of distance-regular graphs of valency $k\ge 3$ that depend on $k$, $\lambda$ and $\mu$, where $\lambda$ is the number of common neighbors of any two adjacent vertices and $\mu$ is the number of common neighbors of any two vertices in distance two. In many situations, we show that the extendability of a distance-regular graph with valency $k$ grows linearly in $k$. We conjecture that the extendability of a distance-regular graph of even order and valency $k$ is at least $\lceil k/2\rceil -1$ and we prove this fact for bipartite distance-regular graphs.In course of this investigation, we obtain some new bounds for the max-cut and the independence number of distance-regular graphs in terms of their size and odd girth and we prove that our inequalities are incomparable with known eigenvalue bounds for these combinatorial parameters.     

Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs

Consider two graphs $G$ and $H$. Let $H^k\left[G\right]$ be the lexicographic product of $H^k$ and $G$, where $H^k$ is the lexicographic product of the graph $H$ by itself $k$ times. In this paper, we determine the spectrum of $H^k\left[G\right]$ and $H^k$ when $G$ and $H$ are regular and the Laplacian spectrum of $H^k\left[G\right]$ and $H^k$ for $G$ and $H$ arbitrary. Particular emphasis is given to the least eigenvalue of the adjacency matrix in the case of lexicographic powers of regular graphs, and to the algebraic connectivity and the largest Laplacian eigenvalues in the case of lexicographic powers of arbitrary graphs. This approach allows the determination of the spectrum (in case of regular graphs) and Laplacian spectrum (for arbitrary graphs) of huge graphs. As an example, the spectrum of the lexicographic power of the Petersen graph with the googol number (that is, 10¹⁰⁰ ) of vertices is determined. The paper finishes with the extension of some well known spectral and combinatorial invariant properties of graphs to its lexicographic powers.     

New concepts of regular and (highly) irregular vague graphs with applications

In this paper, some types of vague graphs are introdaced such as $d_m$-regular, $t{d}_m$-regular, $m$-highly irregular and $m$-highly totally irregular vague graphs are introduced and some properties of them are discussed. Comparative study between $d_m$-regular ($m$-highly irregular) vague graph and $t{d}_m$-regular ($m$-highly totally irregular) vague graph are done. In addition, $d_m$-regularity and $m$-highly irregularity on some vague graphs, which underlying crisp graphs are a cycle or a path is also studied. Finally, some applications of regular vague graphs are given for demonstration of fullerene molecules, road transport network and wireless multihop networks.     

Mutually describing multisets and integer partitions

To each finite multiset $A$, with underlying set $S\left(A\right)$, we associate a new multiset $d\left(A\right)$, obtained by adjoining to $S\left(A\right)$ the multiplicities of its elements in $A$. We study the orbits of the map $d$ under iteration, and show that if $A$ consists of nonnegative integers, then its orbit under $d$ converges to a cycle. Moreover, we prove that all cycles of $d$ over $\mathbb{Z}$ are of length at most $3$, and we completely determine them. This amounts to finding all systems of mutually describing multisets. In the process, we are led to introduce and study a related discrete dynamical system on the set of integer partitions of $n$ for each $n\ge 1$.