Let Cm and Sm denote a cycle and a star on m edges, respectively. We investigate the decomposition of the complete graphs, Kn, into cycles and stars on the same number of edges. We give an algorithm that determines values of n, for a given value of m, where Kn is {Cm, Sm}-decomposable. We show that the obvious necessary condition is sufficient for such decompositions to exist for different values of m.

A hereditary property R of graphs is said to be reducible if there exist hereditary properties P₁,P₂ such that G ∈ R if and only if the set of vertices of G can be partitioned into V(G) = V₁∪V₂ so that ⟨V₁⟩ ∈ P₁ and ⟨V₂⟩ ∈ P₂. The problem of the factorization of reducible properties into irreducible factors is investigated.

A subgraph H of a graph G is conformal if G - V(H) has a perfect matching. An orientation D of G is Pfaffian if, for every conformal even circuit C, the number of edges of C whose directions in D agree with any prescribed sense of orientation of C is odd. A graph is Pfaffian if it has a Pfaffian orientation. Not every graph is Pfaffian. However, if G has a Pfaffian orientation D, then the determinant of the adjacency matrix of D is the square of the number of perfect matchings of G. (See the book...

A graph $G$ is a $\{d,d+k\}$-graph, if one vertex has degree $d+k$ and the remaining vertices of $G$ have degree $d$. In the special case of $k=0$, the graph $G$ is $d$-regular. Let $k,p\ge 0$ and $d,n\ge 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected $\{d,d+k\}$-graph of order $n$ without a matching $M$ of size $2\left|M\right|=n-p$, then we show in this paper the following: If $d=2$, then $k\ge 2(p+2)$ and (i) $n\ge k+p+6$. If $d\ge 3$ is odd and $t$ an integer with $1\le t\le p+2$, then (ii) $n\ge d+k+1$ for $k\ge d(p+2)$, (iii) $n\ge d(p+3)+2t+1$ for $d(p+2-t)+t\le k\le d(p+3-t)+t-3$, (iv) $n\ge d(p+3)+2p+7$ for $k\le p$. If $d\ge 4$ is even, then (v) $n\ge d+k+2-\eta$ for $k\ge d(p+3)+p+4+\eta$, (vi) $n\ge d+k+p+2-2t=d(p+4)+p+6$ for $k=d(p+3)+4+2t$ and $p\ge 1$, (vii) $n\ge d+k+p+4$ for...

H. Kheddouci, J.F. Saclé and M. Woźniak conjectured in 2000 that if a tree T is not a star, then there is an edge-disjoint placement of T into its third power.In this paper, we prove the conjecture for caterpillars.

The zero forcing number and the positive zero forcing number of a graph are two graph parameters that arise from two types of graph colourings. The zero forcing number is an upper bound on the minimum number of induced paths in the graph that cover all the vertices of the graph, while the positive zero forcing number is an upper bound on the minimum number of induced trees in the graph needed to cover all the vertices in the graph. We show that for a block-cycle graph the zero forcing number equals...