Spectra of strongly Deza graphs

A Deza graph G with parameters $(n,k,b,a)$ is a k-regular graph with n vertices such that any two distinct vertices have b or a common neighbours. The children $G_A$ and $G_B$ of a Deza graph G are defined on the vertex set of G such that every two distinct vertices are adjacent in $G_A$ or $G_B$ if and only if they have a or b common neighbours, respectively. A strongly Deza graph is a Deza graph with strongly regular children. In this paper we give a spectral characterisation of strongly Deza graphs, show relationships between eigenvalues, and study strongly Deza graphs which are distance-regular.     

Maximizing the expected number of components in an online search of a graph

The following optimal stopping problem is considered. The vertices of a graph G are revealed one by one, in a random order, to a selector. He aims to stop this process at a time t that maximizes the expected number of connected components in the graph ${\stackrel{?}{G}}_t$, induced by the currently revealed vertices. The selector knows G in advance, but different versions of the game are considered depending on the information that he gets about ${\stackrel{?}{G}}_t$. We show that when G has N vertices and maximum degree of order $o(\sqrt{N})$, then the number of components of ${\stackrel{?}{G}}_t$ is concentrated around its mean, which implies that playing the optimal strategy the selector does not benefit much by receiving more information about ${\stackrel{?}{G}}_t$. Results of similar nature were previously obtained by M. Lasoń for the case where G is a k-tree (for constant k). We also consider the particular cases where G is a square, triangular or hexagonal lattice, showing that an optimal selector gains cN components and we compute c with an error less than 0.005 in each case.     

Decomposition of cubic graphs with cyclic connectivity 5

Let G be a cyclically 5-connected cubic graph with a 5-edge-cut separating G into two cyclic components $G_1$ and $G_2$. We prove that each component $G_i$ can be completed to a cyclically 5-connected cubic graph by adding three vertices, unless $G_i$ is a cycle of length five. Our work extends similar results by Andersen et al. for cyclic connectivity 4 from 1988.     

A note on Hadwiger’s conjecture for W5-free graphs with independence number two

The Hadwiger number of a graph $G$, denoted $h\left(G\right)$, is the largest integer $t$ such that $G$ contains $K_t$ as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph $G$, $h\left(G\right)\ge \chi \left(G\right)$, where $\chi \left(G\right)$ denotes the chromatic number of $G$. Let $\alpha \left(G\right)$ denote the independence number of $G$. A graph is $H$-free if it does not contain the graph $H$ as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that $h\left(G\right)\ge \chi \left(G\right)$ for all $H$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $H$ is any graph on four vertices with $\alpha \left(H\right)\le 2$, $H=C_5$, or $H$ is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs $H$ on five vertices with $\alpha \left(H\right)\le 2$. In this note, we prove that $h\left(G\right)\ge \chi \left(G\right)$ for all $W_5$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $W_5$ denotes the wheel on six vertices.     

Proximity and remoteness in triangle-free and C4-free graphs in terms of order and minimum degree

Let G be a finite, connected graph. The average distance of a vertex v of G is the arithmetic mean of the distances from v to all other vertices of G. The remoteness $\rho (G)$ and the proximity $\pi (G)$ of G are the maximum and the minimum of the average distances of the vertices of G. In this paper, we present a sharp upper bound on the remoteness of a triangle-free graph of given order and minimum degree, and a corresponding bound on the proximity, which is sharp apart from an additive constant. We also present upper bounds on the remoteness and proximity of $C_4$-free graphs of given order and minimum degree, and we demonstrate that these are close to being best possible.     

Point partition numbers: Decomposable and indecomposable critical graphs

Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number ${\chi }_t(G)$ is the least integer k for which G admits a coloring with k colors such that each color class induces a $(t?1)$-degenerate subgraph of G. So ${\chi }_1$ is the chromatic number and ${\chi }_2$ is the point arboricity. The point partition number ${\chi }_t$ with $t\ge 1$ was introduced by Lick and White. A graph G is called ${\chi }_t$-critical if every proper subgraph H of G satisfies ${\chi }_t(H)<{\chi }_t(G)$. In this paper we prove that if G is a ${\chi }_t$-critical graph whose order satisfies $|G|\le 2{\chi }_t(G)?2$, then G can be obtained from two non-empty disjoint subgraphs $G_1$ and $G_2$ by adding t edges between any pair $u,v$ of vertices with $u\in V(G_1)$ and $v\in V(G_2)$. Based on this result we establish the minimum number of edges possible in a ${\chi }_t$-critical graph G of order n and with ${\chi }_t(G)=k$, provided that $n\le 2k?1$ and t is even. For $t=1$ the corresponding two results were obtained in 1963 by Tibor Gallai.     

Cube-complements of generalized Fibonacci cubes

The generalized Fibonacci cube $Q_h\left(f\right)$ is the graph obtained from the $h$-cube $Q_h$ by removing all vertices that contain a given binary string $f$ as a substring. If $G$ is an induced subgraph of $Q_h$, then the cube-complement of $G$ is the graph induced by the vertices of $Q_h$ which are not in $G$. In particular, the cube-complement of a generalized Fibonacci cube $Q_h\left(f\right)$ is the subgraph of $Q_h$ induced by the set of all vertices that contain $f$ as a substring. The questions whether a cube-complement of a generalized Fibonacci cube is (i) connected, (ii) an isometric subgraph of a hypercube or (iii) a median graph are studied. Questions (ii) and (iii) are completely solved, i.e. the sets of binary strings that allow a graph of this class to be an isometric subgraph of a hypercube or a median graph are given. The cube-complement of a daisy cube is also studied.     

Domination versus total domination in claw-free cubic graphs

A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, every vertex in S is adjacent to some other vertex in S, then S is a total dominating set. The domination number $\gamma (G)$ of G is the minimum cardinality of a dominating set in G, while the total domination number ${\gamma }_t(G)$ of G is the minimum cardinality of total dominating set in G. A claw-free graph is a graph that does not contain $K_{1,3}$ as an induced subgraph. Let G be a connected, claw-free, cubic graph of order n. We show that if we exclude two graphs, then $\frac{{\gamma }_t(G)}{\gamma (G)}\le \frac{12}{7}$, and this bound is best possible. In order to prove this result, we prove that if we exclude four graphs, then ${\gamma }_t(G)\le \frac{3}{7}n$, and this bound is best possible. These bounds improve previously best known results due to Favaron and Henning (2008) [7], Southey and Henning (2010) [19].     

Oddness to resistance ratios in cubic graphs

Let $G$ be a bridgeless cubic graph. Oddness (weak oddness) is defined as the minimum number of odd components in a 2-factor (an even factor) of $G$, denoted as $\omega \left(G\right)$ (Steffen, 2004) (${\omega }^{\prime }\left(G\right)$ Lukot’ka and Mazák (2016)). Oddness and weak oddness have been referred to as measurements of uncolourability (Fiol et al., 2017, Lukot’ka and Mazák, 2016, Lukot’ka et al., 2015 and, Steffen, 2004), due to the fact that $\omega \left(G\right)=0$ and ${\omega }^{\prime }\left(G\right)=0$ if and only if $G$ is 3-edge-colourable. Another so-called measurement of uncolourability is resistance, defined as the minimum number of edges that can be removed from $G$ such that the resulting graph is 3-edge-colourable, denoted as $r\left(G\right)$ (Steffen, 2004). It is easily shown that $\omega \left(G\right)\ge {\omega }^{\prime }\left(G\right)\ge r\left(G\right)$. While it has been shown that the difference between any two of these measures can be arbitrarily large, it has been conjectured that ${\omega }^{\prime }\left(G\right)\le 2r\left(G\right)$, and that if $G$ is a snark then $\omega \left(G\right)\le 2r\left(G\right)$ (Fiol et al., 2017). In this paper, we disprove the latter by showing that the ratio of oddness to weak oddness can be arbitrarily large. We also offer some insights into the former conjecture by defining what we call resistance reducibility, and hypothesizing that almost all cubic graphs are such resistance reducible.     

On e-cuspidal pairs of finite groups of exceptional Lie type

Let G be a simple, simply connected algebraic group of exceptional type defined over ${\mathbb{F}}_q$ with Frobenius endomorphism $F:G\to G$. Let $??q$ be a good prime for G. We determine the number of irreducible Brauer characters in the quasi-isolated ?-blocks of $G^F$. This is done by proving that generalized e-Harish-Chandra theory holds for the Lusztig series associated to quasi-isolated elements of $G^{?F}$.     

Optimization of eigenvalue bounds for the independence and chromatic number of graph powers

The $k^{\text{th}}$ power of a graph $G=(V,E)$, $G^k$, is the graph whose vertex set is V and in which two distinct vertices are adjacent if and only if their distance in G is at most k. This article proves various eigenvalue bounds for the independence number and chromatic number of $G^k$ which purely depend on the spectrum of G, together with a method to optimize them. Our bounds for the k-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general, thus justifying the use of integer programming to optimize them. Some of the bounds previously known in the literature follow as a corollary of our main results. Infinite families of graphs where the bounds are sharp are presented as well.     

Quasisymmetric and Schur expansions of cycle index polynomials

Given a subgroup $G$ of the symmetric group $S_n$, the cycle index polynomial ${\mathrm{cyc}}_G$ is the average of the power-sum symmetric polynomials indexed by the cycle types of permutations in $G$. By Pólya’s Theorem, the monomial expansion of ${\mathrm{cyc}}_G$ is the generating function for weighted colorings of $n$ objects, where we identify colorings related by one of the symmetries in $G$. This paper develops combinatorial formulas for the fundamental quasisymmetric expansions and Schur expansions of certain cycle index polynomials. We give explicit bijective proofs based on standardization algorithms applied to equivalence classes of colorings. Subgroups studied here include Young subgroups of $S_n$, the alternating groups $A_n$, direct products, conjugate subgroups, and certain cyclic subgroups of $S_n$ generated by $(1,2,\dots ,k)$. The analysis of these cyclic subgroups when $k$ is prime reveals an unexpected connection to perfect matchings on a hypercube with certain vertices identified.     

On the k-planar local crossing number

Given a fixed positive integer $k$, the $k$-planar local crossing number of a graph $G$, denoted by ${\text{<mi mathsize="small" is="true">LCR</mi>}}_k\left(G\right)$, is the minimum positive integer $L$ such that $G$ can be decomposed into $k$ subgraphs, each of which can be drawn in a plane such that no edge is crossed more than $L$ times. In this note, we show that under certain natural restrictions, the ratio ${\text{<mi mathsize="small" is="true">LCR</mi>}}_k\left(G\right)∕{\text{<mi mathsize="small" is="true">LCR</mi>}}_1\left(G\right)$ is of order $1∕k^2$, which is analogous to the result of Pach et al. (2018) for the $k$-planar crossing number ${\text{<mi mathsize="small" is="true">CR</mi>}}_k\left(G\right)$ (defined as the minimum positive integer $C$ for which there is a $k$-planar drawing of $G$ with $C$ total edge crossings). As a corollary of our proof we show that, under similar restrictions, one may obtain a $k$-planar drawing of $G$ with both the total number of edge crossings as well as the maximum number of times any edge is crossed essentially matching the best known bounds. Our proof relies on the crossing number inequality and several probabilistic tools such as concentration of measure and the Lovász local lemma.     

An improvement to the Hilton-Zhao vertex-splitting conjecture

For a simple graph G, denote by n, $\mathrm{\Delta }(G)$, and ${\chi }^{\prime }(G)$ its order, maximum degree, and chromatic index, respectively. A graph G is edge-chromatic critical if ${\chi }^{\prime }(G)=\mathrm{\Delta }(G)+1$ and ${\chi }^{\prime }(H)<{\chi }^{\prime }(G)$ for every proper subgraph H of G. Let G be an n-vertex connected regular class 1 graph, and let $G^{?}$ be obtained from G by splitting one vertex of G into two vertices. Hilton and Zhao in 1997 conjectured that $G^{?}$ must be edge-chromatic critical if $\mathrm{\Delta }(G)>n/3$, and they verified this when $\mathrm{\Delta }(G)\ge \frac{n}{2}(\sqrt{7}?1)\approx 0.82n$. In this paper, we prove it for $\mathrm{\Delta }(G)\ge 0.75n$.