Reconfiguration graphs of shortest paths

For a graph $G$ and$a,b\in V\left(G\right)$, the shortest path reconfiguration graph of $G$ with respect to $a$ and$b$ is denoted by $S(G,a,b)$. The vertex set of $S(G,a,b)$ is the set of all shortest paths between $a$ and$b$ in $G$. Two vertices in $V\left(S(G,a,b)\right)$ are adjacent, if their corresponding paths in $G$ differ by exactly one vertex. This paper examines the properties of shortest path graphs. Results include establishing classes of graphs that appear as shortest path graphs, decompositions and sums involving shortest path graphs, and the complete classification of shortest path graphs with girth 5 or greater. We include an infinite family of well structured examples, showing that the shortest path graph of a grid graph is an induced subgraph of a lattice.     

Counting arithmetical structures on paths and cycles

Let $G$ be a finite, connected graph. An arithmetical structure on $G$ is a pair of positive integer vectors $\mathbf{d},\mathbf{r}$ such that $(diag\left(\mathbf{d}\right)?A)\mathbf{r}=0$, where $A$ is the adjacency matrix of $G$. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices $(diag\left(\mathbf{d}\right)?A)$). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients $\left(\genfrac{}{}{0ex}{}{2n?1}{n?1}\right)$, and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.     

On graphs with largest possible game domination number

Let $\gamma \left(G\right)$ and ${\gamma }_g\left(G\right)$ be the domination number and the game domination number of a graph $G$, respectively. In this paper ${\gamma }_g$-maximal graphs are introduced as the graphs $G$ for which ${\gamma }_g\left(G\right)=2\gamma \left(G\right)?1$ holds. Large families of ${\gamma }_g$-maximal graphs are constructed among the graphs in which their sets of support vertices are minimum dominating sets. ${\gamma }_g$-maximal graphs are also characterized among the starlike trees, that is, trees which have exactly one vertex of degree at least $3$.     

Diameter bounds and recursive properties of Full-Flag Johnson graphs

The Johnson graphs $J(n,k)$ are a well-known family of combinatorial graphs whose applications and generalizations have been studied extensively in the literature. In this paper, we present a new variant of the family of Johnson graphs, the Full-Flag Johnson graphs, and discuss their combinatorial properties. We show that the Full-Flag Johnson graphs are Cayley graphs on $S_n$ generated by certain well-known classes of permutations and that they are in fact generalizations of permutahedra. We prove a tight $\Theta (n^2∕k^2)$ bound for the diameter of the Full-Flag Johnson graph FJ$(n,k)$ and establish recursive relations between FJ$(n,k)$ and the lower-order Full-Flag Johnson graphs FJ$(n?1,k)$ and FJ$(n?1,k?1)$. We apply this recursive structure to partially compute the spectrum of permutahedra.     

Generalizing Tutte’s theorem and maximal non-matchable graphs

A graph $G$ has a perfect matching if and only if $0$ is not a root of its matching polynomial $\mu (G,x)$. Thus, Tutte’s famous theorem asserts that $0$ is not a root of $\mu (G,x)$ if and only if $c_{\mathrm{odd}}(G?S)\le \left|S\right|$ for all $S?V\left(G\right)$, where $c_{\mathrm{odd}}\left(G\right)$ denotes the number of odd components of $G$. Tutte’s theorem can be proved using a characterization of the structure of maximal non-matchable graphs, that is, the edge-maximal graphs among those having no perfect matching. In this paper, we prove a generalized version of Tutte’s theorem in terms of avoiding any given real number $\theta$ as a root of $\mu (G,x)$. We also extend maximal non-matchable graphs to maximal $\theta$-non-matchable graphs and determine the structure of such graphs.     

Partitioning edge-coloured complete symmetric digraphs into monochromatic complete subgraphs

Let ${\overrightarrow{K}}_{\mathbb{N}}$ be the complete symmetric digraph on the positive integers. Answering a question of DeBiasio and McKenney, we construct a 2-colouring of the edges of ${\overrightarrow{K}}_{\mathbb{N}}$ in which every monochromatic path has density 0.However, if we restrict the length of monochromatic paths in one colour, then no example as above can exist: We show that every $(r+1)$-edge-coloured complete symmetric digraph (of arbitrary infinite cardinality) containing no directed paths of edge-length ${?}_i$ for any colour $i\le r$ can be covered by ${\prod }_{i\in \left[r\right]}{?}_i$ pairwise disjoint monochromatic complete symmetric digraphs in colour $r+1$.Furthermore, we present a stability version for the countable case of the latter result: We prove that the edge-colouring is uniquely determined on a large subgraph, as soon as the upper density of monochromatic paths in colour $r+1$ is bounded by ${\prod }_{i\in \left[r\right]}\frac{1}{{?}_i}$.     

Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in $O\left(n^3\right)$-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in $O\left(n^4\right)$-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs.     

Indicated coloring of graphs

We study a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent realization of this project. The smallest number of colors necessary for Ann to win the game on a graph $G$ (regardless of Ben’s strategy) is called the indicated chromatic number of $G$, and denoted by ${\chi }_i\left(G\right)$. We approach the question how much ${\chi }_i\left(G\right)$ differs from the usual chromatic number $\chi \left(G\right)$. In particular, whether there is a function $f$ such that ${\chi }_i\left(G\right)?f\left(\chi \left(G\right)\right)$ for every graph $G$. We prove that $f$ cannot be linear with leading coefficient less than $4/3$. On the other hand, we show that the indicated chromatic number of random graphs is bounded roughly by $4\chi \left(G\right)$. We also exhibit several classes of graphs for which ${\chi }_i\left(G\right)=\chi \left(G\right)$ and show that this equality for any class of perfect graphs implies Clique-Pair Conjecture for this class of graphs.     

Large values of the clustering coefficient

A prominent parameter in the context of network analysis, originally proposed by Watts and Strogatz (1998), is the clustering coefficient of a graph $G$. It is defined as the arithmetic mean of the clustering coefficients of its vertices, where the clustering coefficient of a vertex $u$ of $G$ is the relative density $m\left(G\left[N_G\left(u\right)\right]\right)∕\left(\genfrac{}{}{0ex}{}{d_G\left(u\right)}{2}\right)$ of its neighborhood if $d_G\left(u\right)$ is at least $2$, and $0$ otherwise. It is unknown which graphs maximize the clustering coefficient among all connected graphs of given order and size.We determine the maximum clustering coefficients among all connected regular graphs of a given order, as well as among all connected subcubic graphs of a given order. In both cases, we characterize all extremal graphs. Furthermore, we determine the maximum increase of the clustering coefficient caused by adding a single edge.     

Throttling for the game of Cops and Robbers on graphs

We consider the cop-throttling number of a graph $G$ for the game of Cops and Robbers, which is defined to be the minimum of $(k+{\mathrm{capt}}_k\left(G\right))$, where $k$ is the number of cops and ${\mathrm{capt}}_k\left(G\right)$ is the minimum number of rounds needed for $k$ cops to capture the robber on $G$ over all possible games. We provide some tools for bounding the cop-throttling number, including showing that the positive semidefinite (PSD) throttling number, a variant of zero forcing throttling, is an upper bound for the cop-throttling number. We also characterize graphs having low cop-throttling number and investigate how large the cop-throttling number can be for a given graph. We consider trees, unicyclic graphs, incidence graphs of finite projective planes (a Meyniel extremal family of graphs), a family of cop-win graphs with maximum capture time, grids, and hypercubes. All the upper bounds on the cop-throttling number we obtain for families of graphs are $O\left(\sqrt{n}\right)$.     

Restrained bondage in graphs

Let $G=(V,E)$ be a graph. A set $S?V$ is a restrained dominating set if every vertex not in $S$ is adjacent to a vertex in $S$ and to a vertex in $V?S$. The restrained domination number of $G$, denoted by ${\gamma }_r\left(G\right)$, is the smallest cardinality of a restrained dominating set of $G$. We define the restrained bondage number $b_r\left(G\right)$ of a nonempty graph $G$ to be the minimum cardinality among all sets of edges $E^{\prime }?E$ for which ${\gamma }_r(G?E^{\prime })>{\gamma }_r\left(G\right)$. Sharp bounds are obtained for $b_r\left(G\right)$, and exact values are determined for several classes of graphs. Also, we show that the decision problem for $b_r\left(G\right)$ is NP-complete even for bipartite graphs.