Problems on matchings and independent sets of a graph

Let $G$ be a finite simple graph. For $X?V\left(G\right)$, the difference of $X$, $d\left(X\right)?\left|X\right|?\left|N\left(X\right)\right|$ where $N\left(X\right)$ is the neighborhood of $X$ and $max\{d\left(X\right):X?V\left(G\right)\}$ is called the critical difference of $G$. $X$ is called a critical set if $d\left(X\right)$ equals the critical difference and $\ker \left(G\right)$ is the intersection of all critical sets. $\mathrm{diadem}\left(G\right)$ is the union of all critical independent sets. An independent set $S$ is an inclusion minimal set with$d\left(S\right)>0$ if no proper subset of $S$ has positive difference.A graph $G$ is called a König–Egerváry graph if the sum of its independence number $\alpha \left(G\right)$ and matching number $\mu \left(G\right)$ equals $\left|V\left(G\right)\right|$.In this paper, we prove a conjecture which states that for any graph the number of inclusion minimal independent set $S$ with $d\left(S\right)>0$ is at least the critical difference of the graph.We also give a new short proof of the inequality $\left|\ker \left(G\right)\right|+\left|\mathrm{diadem}\left(G\right)\right|\le 2\alpha \left(G\right)$.A characterization of unicyclic non-König–Egerváry graphs is also presented and a conjecture which states that for such a graph $G$, the critical difference equals $\alpha \left(G\right)?\mu \left(G\right)$, is proved.We also make an observation about $\ker \left(G\right)$ using Edmonds–Gallai Structure Theorem as a concluding remark.     

Forbidden subgraphs for chorded pancyclicity

We call a graph $G$ pancyclic if it contains at least one cycle of every possible length $m$, for $3\le m\le \left|V\left(G\right)\right|$. In this paper, we define a new property called chorded pancyclicity. We explore forbidden subgraphs in claw-free graphs sufficient to imply that the graph contains at least one chorded cycle of every possible length $4,5,\dots ,\left|V\left(G\right)\right|$. In particular, certain paths and triangles with pendant paths are forbidden.     

On 3-stable number conditions in n-connected claw-free graphs

For a subgraph $X$ of $G$, let ${\alpha }_G^3\left(X\right)$ be the maximum number of vertices of $X$ that are pairwise distance at least three in $G$. In this paper, we prove three theorems. Let $n$ be a positive integer, and let $H$ be a subgraph of an $n$-connected claw-free graph $G$. We prove that if $n\ge 2$, then either $H$ can be covered by a cycle in $G$, or there exists a cycle $C$ in $G$ such that ${\alpha }_G^3(H?V\left(C\right))\le {\alpha }_G^3\left(H\right)?n$. This result generalizes the result of Broersma and Lu that $G$ has a cycle covering all the vertices of $H$ if ${\alpha }_G^3\left(H\right)\le n$. We also prove that if $n\ge 1$, then either $H$ can be covered by a path in $G$, or there exists a path $P$ in $G$ such that ${\alpha }_G^3(H?V\left(P\right))\le {\alpha }_G^3\left(H\right)?n?1$. By using the second result, we prove the third result. For a tree $T$, a vertex of $T$ with degree one is called a leaf of $T$. For an integer $k\ge 2$, a tree which has at most $k$ leaves is called a $k$-ended tree. We prove that if ${\alpha }_G^3\left(H\right)\le n+k?1$, then $G$ has a $k$-ended tree covering all the vertices of $H$. This result gives a positive answer to the conjecture proposed by Kano et al. (2012).     

Kirchhoff index in line,subdivision and total graphs of a regular graph

Let $G$ be a connected regular graph and $l\left(G\right)$, $s\left(G\right)$, $t\left(G\right)$ the line, subdivision, total graphs of $G$, respectively. In this paper, we derive formulae and lower bounds of the Kirchhoff index of $l\left(G\right)$, $s\left(G\right)$ and $t\left(G\right)$, respectively. In particular, we give special formulae for the Kirchhoff index of $l\left(G\right)$, $s\left(G\right)$ and $t\left(G\right)$, where $G$ is a complete graph $K_n$, a regular complete bipartite graph $K_{n,n}$ and a cycle $C_n$.     

Homomorphism complexes and k-cores

For any fixed graph $G$, we prove that the topological connectivity of the graph homomorphism complex Hom($G,K_m$) is at least $m?D\left(G\right)?2$, where $D\left(G\right)={max}_{H?G}\delta \left(H\right)$, for $\delta \left(H\right)$ the minimum degree of a vertex in a subgraph $H$. This generalizes a theorem of C?uki? and Kozlov, in which the maximum degree $\Delta \left(G\right)$ was used in place of $D\left(G\right)$, and provides a high-dimensional analogue of the graph theoretic bound for chromatic number, $\chi \left(G\right)\le D\left(G\right)+1$, as $\chi \left(G\right)=min\{m:\text{Hom}(G,K_m)\ne ?\}$. Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom$(G(n,p),K_m)$ when $p=c∕n$ for a fixed constant $c>0$.     

Distinguishing chromatic number of random Cayley graphs

The distinguishing chromatic number of a graph $G$, denoted ${\chi }_D\left(G\right)$, is defined as the minimum number of colors needed to properly color $G$ such that no non-trivial automorphism of $G$ fixes each color class of $G$. In this paper, we consider random Cayley graphs $\Gamma$ defined over certain abelian groups $A$ with $\left|A\right|=n$, and show that with probability at least $1?n^{?\Omega (logn)}$, ${\chi }_D\left(\Gamma \right)\le \chi \left(\Gamma \right)+1$.     

A new formula for the decycling number of regular graphs

The decycling number $?\left(G\right)$ of a graph $G$ is the smallest number of vertices which can be removed from $G$ so that the resultant graph contains no cycle. A decycling set containing exactly $?\left(G\right)$ vertices of $G$ is called a $?$-set. For any decycling set $S$ of a $k$-regular graph $G$, we show that $\left|S\right|=\frac{\beta \left(G\right)+m\left(S\right)}{k?1}$, where $\beta \left(G\right)$ is the cycle rank of $G$, $m\left(S\right)=c+\left|E\left(S\right)\right|?1$ is the margin number of $S$, $c$ and $\left|E\left(S\right)\right|$ are, respectively, the number of components of $G?S$ and the number of edges in $G\left[S\right]$. In particular, for any $?$-set $S$ of a 3-regular graph $G$, we prove that $m\left(S\right)=\xi \left(G\right)$, where $\xi \left(G\right)$ is the Betti deficiency of $G$. This implies that the decycling number of a 3-regular graph $G$ is $\frac{\beta \left(G\right)+\xi \left(G\right)}{2}$. Hence $?\left(G\right)=?\frac{\beta \left(G\right)}{2}?$ for a 3-regular upper-embeddable graph $G$, which concludes the results in [Gao et al., 2015, Wei and Li, 2013] and solves two open problems posed by Bau and Beineke (2002). Considering an algorithm by Furst et al., (1988), there exists a polynomial time algorithm to compute $Z\left(G\right)$, the cardinality of a maximum nonseparating independent set in a $3$-regular graph $G$, which solves an open problem raised by Speckenmeyer (1988). As for a 4-regular graph $G$, we show that for any $?$-set $S$ of $G$, there exists a spanning tree $T$ of $G$ such that the elements of $S$ are simply the leaves of $T$ with at most two exceptions providing $?\left(G\right)=?\frac{\beta \left(G\right)}{3}?$. On the other hand, if $G$ is a loopless graph on $n$ vertices with maximum degree at most $4$, then

The above two upper bounds are tight, and this makes an extension of a result due to Punnim (2006).     

On maximum matchings in König–Egerváry graphs

For a graph $G$ let $\alpha \left(G\right),\mu \left(G\right)$, and $\tau \left(G\right)$ denote its independence number, matching number, and vertex cover number, respectively. If $\alpha \left(G\right)+\mu \left(G\right)=\left|V\left(G\right)\right|$ or, equivalently, $\mu \left(G\right)=\tau \left(G\right)$, then $G$ is a König–Egerváry graph.In this paper we give a new characterization of König–Egerváry graphs.     

A sharp lower bound on Steiner Wiener index for trees with given diameter

Let $G$ be a connected graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. For a subset $S$ of $V\left(G\right)$, the Steiner distance$d\left(S\right)$ of $S$ is the minimum size of a connected subgraph whose vertex set contains $S$. For an integer $k$ with $2\le k\le n?1$, the Steiner$k$-Wiener index${\text{SW}}_k\left(G\right)$ is ${\sum }_{S?V\left(G\right),\left|S\right|=k}d\left(S\right)$. In this paper, we introduce some transformations for trees that do not increase their Steiner $k$-Wiener index for $2\le k\le n?1$. Using these transformations, we get a sharp lower bound on Steiner $k$-Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well.     

Equitable Δ-coloring of graphs

Consider a graph $G$ consisting of a vertex set $V\left(G\right)$ and an edge set $E\left(G\right)$. Let $\Delta \left(G\right)$ and $\chi \left(G\right)$ denote the maximum degree and the chromatic number of $G$, respectively. We say that $G$ is equitably $\Delta \left(G\right)$-colorable if there exists a proper $\Delta \left(G\right)$-coloring of $G$ such that the sizes of any two color classes differ by at most one. Obviously, if $G$ is equitably $\Delta \left(G\right)$-colorable, then $\Delta \left(G\right)\ge \chi \left(G\right)$. Conversely, even if $G$ satisfies $\Delta \left(G\right)\ge \chi \left(G\right)$, we cannot guarantee that $G$ must be equitably $\Delta \left(G\right)$-colorable. In 1994, the Equitable $\Delta$-Coloring Conjecture $\left(E\Delta \mathrm{CC}\right)$ asserts that a connected graph $G$ with $\Delta \left(G\right)\ge \chi \left(G\right)$ is equitably $\Delta \left(G\right)$-colorable if $G$ is different from $K_{2n+1,2n+1}$ for all $n\ge 1$. In this paper, we give necessary conditions for a graph $G$ (not necessarily connected) with $\Delta \left(G\right)\ge \chi \left(G\right)$ to be equitably $\Delta \left(G\right)$-colorable and prove that those necessary conditions are also sufficient conditions when $G$ is a bipartite graph, or $G$ satisfies $\Delta \left(G\right)\ge \frac{\left|V\left(G\right)\right|}{3}+1$, or $G$ satisfies $\Delta \left(G\right)\le 3$.     

b-coloring of Kneser graphs

A $b$-coloring of a graph $G$ with $k$ colors is a proper coloring of $G$ using $k$ colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer $k$ for which $G$ has a $b$-coloring using $k$ colors is the $b$-chromatic number $b\left(G\right)$ of $G$. The $b$-spectrum $S_b\left(G\right)$ of a graph $G$ is the set of positive integers $k,\chi \left(G\right)\le k\le b\left(G\right)$, for which $G$ has a $b$-coloring using $k$ colors. A graph $G$ is $b$-continuous if $S_b\left(G\right)$ = the closed interval $[\chi \left(G\right),b\left(G\right)]$. In this paper, we obtain an upper bound for the $b$-chromatic number of some families of Kneser graphs. In addition we establish that $[\chi \left(G\right),n+k+1]?S_b\left(G\right)$ for the Kneser graph $G=K(2n+k,n)$ whenever $3\le n\le k+1$. We also establish the $b$-continuity of some families of regular graphs which include the family of odd graphs.     

Some Ramsey–Turán type problems and related questions

In this paper the following Ramsey–Turán type problem is one of several addressed. For which graphs $G$ does there exist a constant $0<c<1$ such that when $H$ is a graph of order the Ramsey number $r\left(G\right)$ with $\delta \left(H\right)>c\left|H\right|$, then any 2-edge coloring of $H$ contains a monochromatic copy of $G$? Specific results, conjectures, and questions with suggested values for $c$ are considered when $G$ is an odd cycle, path, or tree of limited maximum degree. Another variant is to 2-edge color a replacement for the graph $K_{r\left(G\right)}$ by a balanced multipartite graph of approximately the same order with the same consequence, a monochromatic $G$.