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.     

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.     

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$.     

Structure and algorithms for (cap,even hole)-free graphs

A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph $G$ has a vertex of degree at most $\frac{3}{2}\omega \left(G\right)?1$, and hence $\chi \left(G\right)\le \frac{3}{2}\omega \left(G\right)$, where $\omega \left(G\right)$ denotes the size of a largest clique in $G$ and $\chi \left(G\right)$ denotes the chromatic number of $G$. We give an $O\left(nm\right)$ algorithm for $q$-coloring these graphs for fixed $q$ and an $O\left(nm\right)$ algorithm for maximum weight stable set, where $n$ is the number of vertices and $m$ is the number of edges of the input graph. We also give a polynomial-time algorithm for minimum coloring.Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs $G$ without clique cutsets have treewidth at most $6\omega \left(G\right)?1$ and clique-width at most 48.     

Distant sum distinguishing index of graphs

Consider a positive integer $r$ and a graph $G=(V,E)$ with maximum degree $\Delta$ and without isolated edges. The least $k$ so that a proper edge colouring $c:E\to \{1,2,\dots ,k\}$ exists such that ${\sum }_{e?u}c\left(e\right)\ne {\sum }_{e?v}c\left(e\right)$ for every pair of distinct vertices $u,v$ at distance at most $r$ in $G$ is denoted by ${\chi }_{\Sigma ,r}^{\prime }\left(G\right)$. For $r=1$, it has been proved that ${\chi }_{\Sigma ,1}^{\prime }\left(G\right)=(1+o\left(1\right))\Delta$. For any $r\ge 2$ in turn an infinite family of graphs is known with ${\chi }_{\Sigma ,r}^{\prime }\left(G\right)=\Omega \left({\Delta }^{r?1}\right)$. We prove that, on the other hand, ${\chi }_{\Sigma ,r}^{\prime }\left(G\right)=O\left({\Delta }^{r?1}\right)$ for $r\ge 2$. In particular, we show that ${\chi }_{\Sigma ,r}^{\prime }\left(G\right)\le 6{\Delta }^{r?1}$ if $r\ge 4$.     

Saturating sets in projective planes and hypergraph covers

Let ${\Pi }_q$ be an arbitrary finite projective plane of order $q$. A subset $S$ of its points is called saturating if any point outside $S$ is collinear with a pair of points from $S$. Applying probabilistic tools we improve the upper bound on the smallest possible size of the saturating set to $?\sqrt{3qlnq}?+?(\sqrt{q}+1)∕2?$. The same result is presented using an algorithmic approach as well, which points out the connection with the transversal number of uniform multiple intersecting hypergraphs.     

List star chromatic index of sparse graphs

A star edge-coloring of a graph $G$ is a proper edge coloring such that every 2-colored connected subgraph of $G$ is a path of length at most 3. For a graph $G$, let the list star chromatic index of $G$, $c{h}_s^{\prime }\left(G\right)$, be the minimum $k$ such that for any $k$-uniform list assignment $L$ for the set of edges, $G$ has a star edge-coloring from $L$. Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph $G$ is less than $\frac{14}{5}$ (resp. 3), then $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+2$ (resp. $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+3$).     

The strong chromatic index of Halin graphs

A strong edge coloring of a graph $G$ is an assignment of colors to the edges of $G$ such that two distinct edges are colored differently if their distance is at most two. The strong chromatic index of a graph $G$, denoted by $s{\chi }^{\prime }\left(G\right)$, is the minimum number of colors needed for a strong edge coloring of $G$. A Halin graph $G$ is a plane graph constructed from a tree $T$ without vertices of degree two by connecting all leaves through a cycle $C$. If a Halin graph $G=T\cup C$ is different from a certain necklace $N{e}_2$ and any wheel $W_n$, $n?0(mod3)$, then we prove that $s{\chi }^{\prime }\left(G\right)?s{\chi }^{\prime }\left(T\right)+3$.     

Exponential independence

For a set $S$ of vertices of a graph $G$, a vertex $u$ in $V\left(G\right)?S$, and a vertex $v$ in $S$, let ${\mathrm{dist}}_{(G,S)}(u,v)$ be the distance of $u$ and $v$ in the graph $G?(S?\left\{v\right\})$. Dankelmann et al. (2009) define $S$ to be an exponential dominating set of $G$ if $w_{(G,S)}\left(u\right)\ge 1$ for every vertex $u$ in $V\left(G\right)?S$, where $w_{(G,S)}\left(u\right)={\sum }_{v\in S}{\left(\frac{1}{2}\right)}^{{\mathrm{dist}}_{(G,S)}(u,v)?1}$. Inspired by this notion, we define $S$ to be an exponential independent set of $G$ if $w_{(G,S?\left\{u\right\})}\left(u\right)<1$ for every vertex $u$ in $S$, and the exponential independence number ${\alpha }_e\left(G\right)$ of $G$ as the maximum order of an exponential independent set of $G$.Similarly as for exponential domination, the non-local nature of exponential independence leads to many interesting effects and challenges. Our results comprise exact values for special graphs as well as tight bounds and the corresponding extremal graphs. Furthermore, we characterize all graphs $G$ for which ${\alpha }_e\left(H\right)$ equals the independence number $\alpha \left(H\right)$ for every induced subgraph $H$ of $G$, and we give an explicit characterization of all trees $T$ with ${\alpha }_e\left(T\right)=\alpha \left(T\right)$.     

Universal point sets for planar three-trees

For every $n\in \mathbb{N}$, we present a set $S_n$ of $O(n^{3/2}\log n)$ points in the plane such that every planar 3-tree with n vertices has a straight-line embedding in the plane in which the vertices are mapped to a subset of $S_n$. This is the first subquadratic upper bound on the cardinality of universal point sets for planar 3-trees, as well as for the class of 2-trees and serial parallel graphs.     

On strong graph bundles

We study strong graph bundles : a concept imported from topology which generalizes both covering graphs and product graphs. Roughly speaking, a strong graph bundle always involves three graphs $E$, $B$ and $F$ and a projection $p:E\to B$ with fiber $F$ (i.e. $p^{?1}\left(x\right)?F$ for all $x\in V\left(B\right)$) such that the preimage of any edge $xy$ of $B$ is trivial (i.e. $p^{?1}\left(xy\right)?K_2?F$). Here we develop a framework to study which subgraphs $S$ of $B$ have trivial preimages (i.e. $p^{?1}\left(S\right)?S?F$) and this allows us to compare and classify several variations of the concept of strong graph bundle. As an application, we show that the clique operator preserves triangular graph bundles (strong graph bundles where preimages of triangles are trivial) thus yielding a new technique for the study of clique divergence of graphs.     

Essential edge connectivity of line graphs

Let $G$ be a graph and $L\left(G\right)$ be its line graph. In 1969, Chartrand and Stewart proved that ${\kappa }^{\prime }\left(L\left(G\right)\right)\ge 2{\kappa }^{\prime }\left(G\right)?2$, where ${\kappa }^{\prime }\left(G\right)$ and ${\kappa }^{\prime }\left(L\left(G\right)\right)$ denote the edge connectivity of $G$ and $L\left(G\right)$ respectively. We show a similar relationship holds for the essential edge connectivity of $G$ and $L\left(G\right)$, written ${\kappa }_e^{\prime }\left(G\right)$ and ${\kappa }_e^{\prime }\left(L\left(G\right)\right)$, respectively. In this note, it is proved that if $L\left(G\right)$ is not a complete graph and $G$ does not have a vertex of degree two, then ${\kappa }_e^{\prime }\left(L\left(G\right)\right)\ge 2{\kappa }_e^{\prime }\left(G\right)?2$. An immediate corollary is that $\kappa \left(L^2\left(G\right)\right)\ge 2\kappa \left(L\left(G\right)\right)?2$ for such graphs $G$, where the vertex connectivity of the line graph $L\left(G\right)$ and the second iterated line graph $L^2\left(G\right)$ are written as $\kappa \left(L\left(G\right)\right)$ and $\kappa \left(L^2\left(G\right)\right)$ respectively.     

Connectivity keeping stars or double-stars in 2-connected graphs

In Mader (2010), Mader conjectured that for every positive integer $k$ and every finite tree $T$ with order $m$, every $k$-connected, finite graph $G$ with $\delta \left(G\right)\ge ?\frac{3}{2}k?+m?1$ contains a subtree $T^{\prime }$ isomorphic to $T$ such that $G?V\left(T^{\prime }\right)$ is $k$-connected. In the same paper, Mader proved that the conjecture is true when $T$ is a path. Diwan and Tholiya (2009) verified the conjecture when $k=1$. In this paper, we will prove that Mader’s conjecture is true when $T$ is a star or double-star and $k=2$.