Independent domination and matchings in graphs

If G is a graph of order n, independent domination number i and matching number α₀, then i+α₀⩽n. We characterize all graphs for which equality holds in this inequality and show that this class can be recognized in polynomial time.     

Independent domination in subcubic graphs of girth at least six

A set $S$ of vertices in a graph $G$ is an independent dominating set of $G$ if $S$ is an independent set and every vertex not in $S$ is adjacent to a vertex in $S$. The independent domination number, $i\left(G\right)$, of $G$ is the minimum cardinality of an independent dominating set. In this paper, we extend the work of Henning, Löwenstein, and Rautenbach (2014) who proved that if $G$ is a bipartite, cubic graph of order $n$ and of girth at least $6$, then $i\left(G\right)\le \frac{4}{11}n$. We show that the bipartite condition can be relaxed, and prove that if $G$ is a cubic graph of order $n$ and of girth at least $6$, then $i\left(G\right)\le \frac{4}{11}n$.     

Independent sets ink-chromatic graphs

A graph is said to have propertyP _k if in eachk-colouring ofG using allk colours there arek independent vertices having all colours. An (unpublished) suggestion of P. Erdős is answered in the affirmative: For eachk≧3 there is a k-critical graph withP _k . With the aid of a construction of T. Gallaik-chromatic graphs (k≧7) withP _k orP _k+1 of arbitrarily high connectivity are obtained. The main result is: Eachk-chromatic graph (k≧3) of girth ≧6 hasP _k or is a circuit of length 7. Dedicated to Paul Erdős on his seventieth birthday     

Independent sets in regular graphs

Lower and upper bounds for the maximal number of independent vertices in a regular graph are obtained, it is shown that the bounds are best possible. Some properties of regular graphs concerning the property ℋ defined below are investigated. This paper is to be a part of the author’s Ph. D. thesis written under the supervision of Prof. B. Grünbaum at the Hebrew University of Jerusalem.     

Independent sets,cliques and hamiltonian graphs

LetG be ak-connected (k 2) graph onn vertices. LetS be an independent set ofG. S is called essential if there exist two distinct vertices inS which have a common neighbor inG. LetV _r, be a clique which is a complete subgraph ofG. In this paper it is proven that if every essential independent setS ofk + 1 vertices satisfiesS V _r , thenG is hamiltonian, orG{u} is hamiltonian for someu V _r, orG is one of three classes of exceptional graphs. Our theorem generalizes several well-known theorems.     

Independent perfect domination sets in Cayley graphs

In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube Q_n has an independent perfect domination set if and only if Q_n is a regular covering of the complete graph K_n+1 if and only if n = 2^m ? 1 for some natural number m. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 213–219, 2001     

Linear colorings of subcubic graphs

A linear coloring of a graph is a proper coloring of the vertices of the graph so that each pair of color classes induces a union of disjoint paths. In this paper, we prove that for every connected graph with maximum degree at most three and every assignment of lists of size four to the vertices of the graph, there exists a linear coloring such that the color of each vertex belongs to the list assigned to that vertex and the neighbors of every degree-two vertex receive different colors, unless the graph is _C5$C_5$ or _K3,3$K_{3,3}$. This confirms a conjecture raised by Esperet, Montassier and Raspaud [L. Esperet, M. Montassier, and A. Raspaud, Linear choosability of graphs, Discrete Math. 308 (2008) 3938–3950]. Our proof is constructive and yields a linear-time algorithm to find such a coloring.     

Bipartite density of triangle-free subcubic graphs

A graph is subcubic if its maximum degree is at most 3. The bipartite density of a graph G is defined as b(G)=max{|E(B)|/|E(G)|:B is a bipartite subgraph of G}. It was conjectured by Bondy and Locke that if G is a triangle-free subcubic graph, then and equality holds only if G is in a list of seven small graphs. The conjecture has been confirmed recently by Xu and Yu. This note gives a shorter proof of this result.     

Strong list-chromatic index of subcubic graphs

A strong $k$-edge-coloring of a graph G is an edge-coloring with $k$ colors in which every color class is an induced matching. The strong chromatic index of $G$, denoted by ${\chi }_s^{\prime }\left(G\right)$, is the minimum $k$ for which $G$ has a strong $k$-edge-coloring. In 1985, Erd?s and Ne?et?il conjectured that ${\chi }_s^{\prime }\left(G\right)\le \frac{5}{4}\Delta {\left(G\right)}^2$, where $\Delta \left(G\right)$ is the maximum degree of $G$. When $G$ is a graph with maximum degree at most 3, the conjecture was verified independently by Andersen and Horák, Qing, and Trotter. In this paper, we consider the list version of strong edge-coloring. In particular, we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10.     

Independent sets in graphs without subtrees with many leaves

A subtree of a graph is called inscribed if no three vertices of the subtree generate a triangle in the graph. We prove that, for fixed k, the independent set problem is solvable in polynomial time for each of the following classes of graphs: (1) graphs without subtrees with k leaves, (2) subcubic graphs without inscribed subtrees with k leaves, and (3) graphs with degree not exceeding k and lacking induced subtrees with four leaves.     

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph $G$ with $\Delta \left(G\right)?\delta \left(G\right)\le 1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for $k$-regular graphs with $4\le k\le 6$. All counterexamples for $k$-regular graphs $(k\ge 7)$ given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $k\le 4$.     

Maximum induced matchings in graphs

We provide a formula for the number of edges of a maximum induced matching in a graph. As applications, we give some structural properties of (k + 1)K₂-free graphs, construct all 2K₂-free graphs, and count the number of labeled 2K₂-free connected bipartite graphs.     

Disjoint matchings of graphs

In this paper, we prove a generalization of the familiar marriage theorem. One way of stating the marriage theorem is: Let G be a bipartite graph, with parts S₁ and S₂. If A ? S₁ and F(A) ? S₂ is the set of neighbors of points in A, then a matching of G exists if and only if Σ_x∈S2 min(1, | F^?1(x) ∩ A |) ≥ | A | for each A ? S₁. Our theorem is that k disjoint matchings of G exist if and only Σ_x∈S2 min (k, | F^?1(x) ∩ A |) ≥ k | A | for each A ? S₁.