A graph is said to be k-factor-critical if the removal of any set of k vertices results in a graph with a perfect matching. We study some properties of k-factor-critical graphs and show that many results on q-extendable graphs can be improved using this concept.

A normal partition of the edges of a cubic graph is a partition into trails (no repeated edge) such that each vertex is the end vertex of exactly one trail of the partition. We investigate this notion and give some results and problems.

A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. In this paper we consider linear partitions of cubic simple graphs for which it is well known that la(G) = 2. A linear partition $L=(L_B,L_R)$ is said to be odd whenever each path of $L_B\cup L_R$ has odd length and semi-odd whenever each path of $L_B$ (or each path of $L_R$) has odd length. In [2] Aldred...

A perfect independent set $I$ of a graph $G$ is defined to be an independent set with the property that any vertex not in $I$ has at least two neighbors in $I$. For a nonnegative integer $k$, a subset $I$ of the vertex set $V\left(G\right)$ of a graph $G$ is said to be $k$-independent, if $I$ is independent and every independent subset $I^{\text{'}}$ of $G$ with $|I^{\text{'}}|\ge |I|-(k-1)$ is a subset of $I$. A set $I$ of vertices of $G$ is a super $k$-independent set of $G$ if $I$ is $k$-independent in the graph $G[I,V(G)-I]$, where $G[I,V(G)-I]$ is the bipartite graph obtained from $G$ by deleting all edges...

A graph having a perfect matching is called $r$-extendable if every matching of size $r$ can be extended to a perfect matching. It is proved that in the hypercube $Q_n$, a matching $S$ with $\left|S\right|\le n$ can be extended to a perfect matching if and only if it does not saturate the neighbourhood of any unsaturated vertex. In particular, $Q_n$ is $r$-extendable for every $r$ with $1\le r\le n-1.$

Let $G=(V_G,E_G)$ be a graph and let $N_G\left[v\right]$ denote the closed neighbourhood of a vertex $v$ in $G$. A function $f:V_G\to \{-1,0,1\}$ is said to be a balanced dominating function (BDF) of $G$ if ${\sum }_{u\in N_G\left[v\right]}f\left(u\right)=0$ holds for each vertex $v\in V_G$. The balanced domination number of $G$, denoted by ${\gamma }_b\left(G\right)$, is defined as $${\gamma }_b\left(G\right)=max\left\{\sum _{v\in V_G}f\left(v\right):f\text{is}\text{a}\text{BDF}\text{of}G\right\}.$$ A graph $G$ is called $d$-balanced if ${\gamma }_b\left(G\right)=0$. The novel concept of balanced domination for graphs is introduced. Some upper bounds on the balanced domination number are established, in which one is the best possible bound and the rest are sharp, all the corresponding...

Let ₁,₂ be additive hereditary properties of graphs. A (₁,₂)-decomposition of a graph G is a partition of E(G) into sets E₁, E₂ such that induced subgraph $G\left[E_i\right]$ has the property ${}_i$, i = 1,2. Let us define a property ₁⊕₂ by G: G has a (₁,₂)-decomposition. A property D is said to be decomposable if there exists nontrivial additive hereditary properties ₁, ₂ such that D = ₁⊕₂. In this paper we determine the completeness of some decomposable properties and we characterize the decomposable properties of completeness...