The e-exchange basis graph and matroid connectedness

Let $M$ be a matroid and $e\in E\left(M\right)$. The $e$-exchange basis graph of $M$ has vertices labeled by bases of $M$, and two vertices are adjacent when the bases labeling them have symmetric difference $\{e,x\}$ for some $x\in E\left(M\right)$. In this paper we show that a connected matroid is exactly a matroid with the property that for every element $e\in E\left(M\right)$, the $e$-exchange basis graph is connected.     

Distinguishing index of maps

The distinguishing number of a group $A$ acting on a finite set $\Omega$, denoted by $D(A,\Omega )$, is the least $k$ such that there is a $k$-coloring of $\Omega$ which is preserved only by elements of $A$ fixing all points in $\Omega$. For a map $M$, also called a cellular graph embedding or ribbon graph, the action of $Aut\left(M\right)$ on the vertex set $V$ gives the distinguishing number $D\left(M\right)$. It is known that $D\left(M\right)\le 2$ whenever $\left|V\right|>10$. The action of $Aut\left(M\right)$ on the edge set $E$ gives the distinguishing index $D^{\prime }\left(M\right)$, which has not been studied before. It is shown that the only maps $M$ with $D^{\prime }\left(M\right)>2$ are the following: the tetrahedron; the maps in the sphere with underlying graphs $C_n$, or $K_{1,n}$ for $n=3,4,5$; a map in the projective plane with underlying graph $C_4$; two one-vertex maps with 4 or 5 edges; one two-vertex map with 4 edges; or any map obtained from these maps using duality or Petrie duality. There are 39 maps in all.     

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.     

On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

A C5-decomposition of the λ-fold line graph of the complete graph

In 1996, Cox and Rodger [Cycle systems of the line graph of the complete graph, J. Graph Theory 21 (1996) 173–182] raised the following question: For what values of $m$ and $n$ does there exist an $m$-cycle decomposition of $L\left(K_n\right)?$ In this paper, the above question is answered for $m=5.$ In fact, it is shown that $L\left(K_n\right)\left(\lambda \right),$ the $\lambda$-fold line graph of the complete graph $K_n,$ has a $C_5$-decomposition if and only if $5\mid \lambda \left(\genfrac{}{}{0ex}{}{n}{2}\right)(n?2)$ and $n\ge 4.$     

Graphs are (1,Δ+1)-choosable

A graph $G$ is $(k,k^{\prime })$-choosable if the following holds: For any list assignment $L$ which assigns to each vertex $v$ a set $L\left(v\right)$ of $k$ real numbers, and assigns to each edge $e$ a set $L\left(e\right)$ of $k^{\prime }$ real numbers, there is a total weighting $?:V\left(G\right)\cup E\left(G\right)\to R$ such that $?\left(z\right)\in L\left(z\right)$ for $z\in V\cup E$, and ${\sum }_{e\in E\left(u\right)}?\left(e\right)+?\left(u\right)\ne {\sum }_{e\in E\left(v\right)}?\left(e\right)+?\left(v\right)$ for every edge $uv$. This paper proves that if $G$ is a connected graph of maximum degree $\Delta \ge 2$, then $G$ is $(1,\Delta +1)$-choosable.     

Relation between the H-rank of a mixed graph and the rank of its underlying graph

Given a simple graph $G=(V_G,E_G)$ with vertex set $V_G$ and edge set $E_G$, the mixed graph $\stackrel{?}{G}$ is obtained from $G$ by orienting some of its edges. Let $H\left(\stackrel{?}{G}\right)$ denote the Hermitian adjacency matrix of $\stackrel{?}{G}$ and $A\left(G\right)$ be the adjacency matrix of $G$. The $H$-rank (resp. rank) of $\stackrel{?}{G}$ (resp. $G$), written as $rk\left(\stackrel{?}{G}\right)$ (resp. $r\left(G\right)$), is the rank of $H\left(\stackrel{?}{G}\right)$ (resp. $A\left(G\right)$). Denote by $d\left(G\right)$ the dimension of cycle space of $G$, that is $d\left(G\right)=\left|E_G\right|?\left|V_G\right|+\omega \left(G\right)$, where $\omega \left(G\right)$ denotes the number of connected components of $G$. In this paper, we concentrate on the relation between the $H$-rank of $\stackrel{?}{G}$ and the rank of $G$. We first show that $?2d\left(G\right)?rk\left(\stackrel{?}{G}\right)?r\left(G\right)?2d\left(G\right)$ for every mixed graph $\stackrel{?}{G}$. Then we characterize all the mixed graphs that attain the above lower (resp. upper) bound. By these obtained results in the current paper, all the main results obtained in Luo et al. (2018); Wong et al. (2016) may be deduced consequently.     

Branch-depth: Generalizing tree-depth of graphs

We present a concept called the branch-depth of a connectivity function, that generalizes the tree-depth of graphs. Then we prove two theorems showing that this concept aligns closely with the notions of tree-depth and shrub-depth of graphs as follows. For a graph $G=(V,E)$ and a subset $A$ of $E$ we let ${\lambda }_G\left(A\right)$ be the number of vertices incident with an edge in $A$ and an edge in $E\setminus A$. For a subset $X$ of $V$, let ${\rho }_G\left(X\right)$ be the rank of the adjacency matrix between $X$ and $V\setminus X$ over the binary field. We prove that a class of graphs has bounded tree-depth if and only if the corresponding class of functions ${\lambda }_G$ has bounded branch-depth and similarly a class of graphs has bounded shrub-depth if and only if the corresponding class of functions ${\rho }_G$ has bounded branch-depth, which we call the rank-depth of graphs.Furthermore we investigate various potential generalizations of tree-depth to matroids and prove that matroids representable over a fixed finite field having no large circuits are well-quasi-ordered by restriction.     

Connected k-dominating graphs

For a graph $G=(V,E)$, the $k$-dominating graph $D_k\left(G\right)$ of $G$ has vertices corresponding to the dominating sets of $G$ having cardinality at most $k$, where two vertices of $D_k\left(G\right)$ are adjacent if and only if the dominating set corresponding to one of the vertices can be obtained from the dominating set corresponding to the second vertex by the addition or deletion of a single vertex. We denote the domination and upper domination numbers of $G$ by $\gamma \left(G\right)$ and $\Gamma \left(G\right)$, respectively, and the smallest integer $\epsilon$ for which $D_k\left(G\right)$ is connected for all $k\ge \epsilon$ by $d_0\left(G\right)$. It is known that $\Gamma \left(G\right)+1\le d_0\left(G\right)\le \left|V\right|$, but constructing a graph $G$ such that $d_0\left(G\right)>\Gamma \left(G\right)+1$ appears to be difficult.We present two related constructions. The first construction shows that for each integer $k\ge 3$ and each integer $r$ such that $1\le r\le k?1$, there exists a graph $G_{k,r}$ such that $\Gamma \left(G_{k,r}\right)=k$, $\gamma \left(G_{k,r}\right)=r+1$ and $d_0\left(G_{k,r}\right)=k+r=\Gamma \left(G\right)+\gamma \left(G\right)?1$. The second construction shows that for each integer $k\ge 3$ and each integer $r$ such that $1\le r\le k?1$, there exists a graph $Q_{k,r}$ such that $\Gamma \left(Q_{k,r}\right)=k$, $\gamma \left(Q_{k,r}\right)=r$ and $d_0\left(Q_{k,r}\right)=k+r=\Gamma \left(G\right)+\gamma \left(G\right)$.     

Constructing sparse Davenport–Schinzel sequences

For any sequence $u$, the extremal function $Ex(u,j,n)$ is the maximum possible length of a $j$-sparse sequence with $n$ distinct letters that avoids $u$. We prove that if $u$ is an alternating sequence $abab\dots$ of length $s$, then $Ex(u,j,n)=\Theta \left(s{n}^2\right)$ for all $j\ge 2$ and $s\ge n$, answering a question of Wellman and Pettie (2018) and extending the result of Roselle and Stanton that $Ex(u,2,n)=\Theta \left(s{n}^2\right)$ for any alternation $u$ of length $s\ge n$ (Roselle and Stanton, 1971).Wellman and Pettie also asked how large must $s\left(n\right)$ be for there to exist $n$-block $DS(n,s\left(n\right))$ sequences of length $\Omega \left(n^{2-o\left(1\right)}\right)$. We answer this question by showing that the maximum possible length of an $n$-block $DS(n,s\left(n\right))$ sequence is $\Omega \left(n^{2-o\left(1\right)}\right)$ if and only if $s\left(n\right)=\Omega \left(n^{1-o\left(1\right)}\right)$. We also show related results for extremal functions of forbidden 0–1 matrices with any constant number of rows and extremal functions of forbidden sequences with any constant number of distinct letters.     

Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles

For any graph $G$ with $a,b\in V\left(G\right)$, a shortest path reconfiguration graph can be formed with respect to $a$ and $b$; we denote such a graph as $S(G,a,b)$. The vertex set of $S(G,a,b)$ is the set of all shortest paths from $a$ to $b$ in $G$ while two vertices $U,W$ in $V\left(S(G,a,b)\right)$ are adjacent if and only if the vertex sets of the paths that represent $U$ and $W$ differ in exactly one vertex. In a recent paper (Asplund et al., 2018), it was shown that shortest path graphs with girth five or greater are exactly disjoint unions of even cycles and paths. In this paper, we extend this result by classifying all shortest path graphs with no induced 4-cycles.     

Proportional choosability: A new list analogue of equitable coloring

In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. A $k$-assignment $L$ for a graph $G$ specifies a list $L\left(v\right)$ of $k$ available colors for each vertex $v$ of $G$. An $L$-coloring assigns a color to each vertex $v$ from its list $L\left(v\right)$. For each color $c$, let $\eta \left(c\right)$ be the number of vertices $v$ whose list $L\left(v\right)$ contains $c$. A proportional$L$-coloring of $G$ is a proper $L$-coloring in which each color $c\in {?}_{v\in V\left(G\right)}L\left(v\right)$ is used $?\eta \left(c\right)∕k?$ or $?\eta \left(c\right)∕k?$ times. A graph $G$ is proportionally$k$-choosable if a proportional $L$-coloring of $G$ exists whenever $L$ is a $k$-assignment for $G$. We show that if a graph $G$ is proportionally $k$-choosable, then every subgraph of $G$ is also proportionally $k$-choosable and also $G$ is proportionally $(k+1)$-choosable, unlike equitable choosability for which analogous claims would be false. We also show that any graph $G$ is proportionally $k$-choosable whenever $k\ge \Delta \left(G\right)+?\left|V\left(G\right)\right|∕2?$, and we use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques.     

On the (3,1)-choosability of planar graphs without adjacent cycles of length 5,6,7

A $(k,d)$-list assignment $L$ of a graph $G$ is a mapping that assigns to each vertex $v$ a list $L\left(v\right)$ of at least $k$ colors satisfying $|L\left(x\right)\cap L\left(y\right)|\le d$ for each edge $xy$. A graph $G$ is $(k,d)$-choosable if there exists an $L$-coloring of $G$ for every $(k,d)$-list assignment $L$. This concept is also known as choosability with separation. In this paper, we prove that any planar graph $G$ is $(3,1)$-choosable if any $i$-cycle is not adjacent to a $j$-cycle, where $5\le i\le 6$ and $5\le j\le 7$.