A number of results on claw-free, paw-free graphs have been presented in the literature. Although the proofs of such results are elegant, sound and valid, it has gone unnoticed that all the results about claw-free, paw-free graphs in the literature are a consequence of a result by Olariu [1]. The note, apart from covering the aforementioned gap, also provides an alternate proof to a result by Faudree and Gould found in [2] in that, an unnoticed consequence resulted in the characterization of claw-free, paw-free graphs.
Let \(G=(V,E)\) be a simple connected graph with vertex set \(V(G)\) and edge set \(E(G)\). A matching is a set of pairwise disjoint edges. The order \(n\) of \(G\) is given by \(n=|V(G)|\). The degree, \(\deg_G(v)\) of \(v\in V(G)\) is the number of edges incident with \(v\) in \(G\). If \(\deg_G(v)=1\), then \(v\) is a pendant vertex. The minimum degree and maximum degree of \(G\) are denoted, respectively by \(\delta(G)\) and \(\Delta(G)\). Moreover, they are given as \(\delta(G)=\displaystyle{\min_{v\in V(G)}}\lbrace \deg_G(v)\rbrace\) and \(\Delta(G)=\displaystyle{\max_{v\in V(G)}}\lbrace \deg_G(v)\rbrace\). The maximum number of pendant vertices in a spanning tree of \(G\) is the leaf number, denoted \(L(G)\). If \(P_i\) is a \(u-v\) path of length \(i\) in \(G\), then the distance between \(u\) and \(v\) in \(G\), denoted \(d_G(u,v)\), is the minimum value of \(i\) for which \(P_i\) exists. Let \(S\subset V(G)\). Then \(S\) is an independent set, if no pair of vertices in \(S\) are adjacent. Let \(X\subseteq V(G)\). The graph induced by \(X\) denoted by \(G[X]\), is the graph with vertex set \(X\) and whose edges are all those in \(G\) each of which is incident with \(2\) vertices of \(X\) in \(G\). A claw is the star \(K_{1,3}\), complete bipartite graph. We may consider that \(K_{1,3}\) is given by \(\lbrace ww_1,ww_2,ww_3\rbrace\). Then any graph isomorphic \(K_{1,3}\cup \lbrace w_2w_3\rbrace\) is a paw. A paw is also called a \(K_{1,3}+\lbrace x\rbrace\) or \(Z_1\) (see [3,4]). Further, for distinct vertices \(x\) and \(y\) not in \(K_{1,3}\), a graph isomorphic to \(K_{1,3}\cup \lbrace w_2w_3,w_2x,w_3y\rbrace\) is called a net. See [5] for diagrams on claws, paws and nets. For an integer \(k\ge 2\), a \(k\)–partite graph is the one whose vertex set can be partitioned into \(k\) different independent sets, say \(V_1,V_2,\cdots,V_k\). If \(k=2\), it is a bipartite graph, for \(k=3\) it is a tripartite graph. In general, for \(k\ge 2\) it is a multi-partite graph. A complete multi-partite graph is a multi-partite graph in which there exists an edge between every pair of vertices from different independent sets. The complete graph \(K_n\) can be regarded as a multi-partite graph in which every partite set is a singleton.
If \(G\) does not contain a particular graph \(H\) as an induced sub-graph where \(H\) is not a cycle, then \(G\) is said to be \(H\)–free or equivalently, \(H\) is a forbidden sub-graph of \(G\). Thus \(G\) is claw-free, if it does not contain a claw as an induced sub-graph and \(G\) is paw-free if it has no induced sub-graph isomorphic to a paw. \(G\) is Hamiltonian if it contains a spanning cycle and traceable if it has a spanning path. If \(G\) has a cycle of length \(l\) for each integer \(l: \ 3\le l\le n\), then \(G\) is a panclyclic graph. \(G\) is said to be pan-connected if for every \(l\), where \(d_G(u,v)\le l\le n-1\) and for each pair of distinct vertices \(u\) and \(v\) in \(G\), there exist a \(u-v\) path of length \(l\). For any pair of distinct vertices \(u\) and \(v\) in \(G\), if we can find a spanning \(u-v\) path of \(G\), then \(G\) is Hamiltonian-connected. \(G\) is homogeneously traceable if for each vertex \(v\) in \(G\) there is a spanning path of \(G\) whose one of its pendant vertices is \(v\). The relationship, \[\begin{aligned} \label{e}\mbox{pan-connected}\Longrightarrow \mbox{pancyclic}\Longrightarrow \mbox{Hamiltonian}\Longrightarrow \mbox{homogeneously traceable}, \end{aligned}\tag{1}\] is well known in the literature, see for instance [4]. However, the reverse implications fail to hold.
Pancyclicity, Hamiltonian-connectedness, Hamiltonicity, traceability, length of longest paths and cycles are path- and cycle-related properties of a graph, see [4,6-10]. Studies date as far back as 1856, see [11]. In such studies, many graph parameters as well as graphs with forbidden sub-graphs have been incorporated, see for example [3,5-9].
Being a complex task to establish path- and cycle-related properties of a graph, Goodman and Hedetniemi [3] succeeded in proving that every \(2\)-connected claw-free, paw-free graph has a spanning cycle. Subsequently, Duffus, Gould and Jacobson [7], showed that every \(2\)-connected, claw-free, net-free graph is Hamiltonian. They also, proved that every connected claw-free, net-free graph contains a spanning path. Later, as an improvement of the previously mentioned result in [3], Gould and Jacobson [4] proved that every \(2\)-connected, claw-free, \(Z_2\)-free graph is either pancyclic or a cycle, which implies that each \(2\)-connected, claw-free, paw-free graph is pancyclic or a cycle. In 1997, Faudree and Gould [2] proved that every \(3\)-connected, claw-free, paw-free graph \(G\) is a complete graph or a complete graph minus a matching and so \(G\) is pan-connected. In their proof [2], they highlighted that a straight forward induction would be used to show that any connected, claw-free, paw-free graph that has a vertex of degree at least \(3\) is a complete graph or a complete graph minus a matching. This note provides an alternate proof to their result. An extension of the previously mentioned result in [3] was given in [12], where it has been deduced that every connected, claw-free, paw-free graph \(G\) is either Hamiltonian or is a path. Although the proofs on the results on claw-free, paw-free graphs were elegant (see for example [2-4, 12,13]), it being a complicated work to establish graph properties, it has gone unnoticed that all results in the literature about claw-free, paw-free graphs are a mere consequence of a 1988 result by Olariu [1] (see Theorem 1). This note covers this gap, in-fact all the aforementioned results on claw-free, paw-free graphs are deduced as corollaries, since a characterization of the class is given.
A standard model in dealing with complicated objects is to decompose them into easier, more malleable ones, see for instance [1,14]. For the purpose of the note, we recall the following result by Olariu [1]:
Theorem 1. [1] A graph \(G\) is a paw-free if and only if each component of \(G\) is triangle-free or complete multipartite.
Following Theorem 1, we realized that all simple, connected, claw-free, paw-free graphs can be specified by applying easy but handy observations from it. Moreover, just like properties of the ubiquitous Petersen graph have been presented in the literature [15], properties of pan-connectedness, Hamiltonian conncetedness, pancyclicity and homogeneous traceability are deduced for claw-free, paw-free graphs. In fact, for readers who are unfamiliar with the aforementioned properties, they would find it easier to track them using the derived class. Although, the properties can be observed from the given class (see also [2]), we find it most convenient to use the following results in order to verify some of the properties:
Theorem 2. [16] Let \(G\) be a simple connected graph of order \(n\) such that for any pair of non-adjacent vertices \(u\) and \(v\) in \(G\), we have \(\deg_G(u)+\deg_G(v)\ge n\). Then \(G\) is Hamiltonian connected or \(G\in {\cal G}_1\cup {\cal G}_2\).
Theorem 3. [10] Let \(G\) be the complete \(k\)-partite graph \(K_{p_1,p_2,\cdots,p_k}\) where \(p_1\le p_2\le \cdots\le p_k\) and \(k\ge 3\). Then the following statements are equivalent:
\(G\) is pan-connected.
\(G\) is Hamiltonian-connected.
\(n\ge 2p_k+1\), where \(n\) is the order of \(G\), that is, \(n=\displaystyle\sum^{k}_{i=1}p_i\).
Linial and Sturtevant [17] put forward the following conjecture which at the present moment has been shown to be true only for \(\delta\le 5\), see [18] for more details:
Conjecture 4. [17]Let \(G\) be a simple connected graph with minimum degree \(\delta\), leaf number \(L(G)\) and order \(n\). Then \(L(G)\ge \dfrac{\delta-2}{\delta+1}n+c_\delta\), where \(c_\delta\) is a positive constant that depends on \(\delta\) only.
In [13], attempts to confirm Conjecture 4 for some paw-free graphs and claw-free, paw-free graphs was made. In fact, for claw-free, paw-free graphs it was pointed out that the authors were not sure as to whether or not there are other graphs attaining the proved bounds apart from the complete graph. The characterization given in this note confirms that every connected claw-free, paw-free graph satisfies the premises and conclusion of Conjecture 4.
The following result characterizes all connected, simple claw-free, paw-free graphs together with some of their properties.
Theorem 5. A simple, connected, graph \(G\) of order \(n\), minimum degree \(\delta\) and maximum degree \(\Delta\) is claw-free and paw-free if and only if \(G\in \lbrace P_n,C_n,K_n-tK_2\rbrace\), where \(P_n\) is a path, \(C_n\) is a cycle and \(K_n-tK_2\) is the graph formed by deleting \(t\) disjoint edges from the complete \(K_n\) graph for \(0\le t\le \lfloor \frac{n}{2}\rfloor\). Moreover, the following properties accompany a simple, connected, claw-free, paw-free graph \(G\):
If \(G\notin \lbrace P_n,C_n\rbrace\), then \(G\) is Hamiltonian-connected.
If \(G\notin \lbrace P_n,C_n\rbrace\), then \(G\) is pan-connected.
If \(G\notin \lbrace P_n,C_n\rbrace\), then \(G\) is pancyclic.
If \(G\neq P_n\), then \(G\) is homogeneously traceable.
If \(G\notin \lbrace P_n,C_n\rbrace\), then \(L(G)=n-2\) or \(n-1\). Hence, every connected, simple, claw-free, paw-free graph satisfies Conjecture 4.
Proof. It is clear that if \(G\in \lbrace P_n,C_n,K_n-tK_2\rbrace\), then \(G\) is a simple, connected, claw-free, paw-free graph. So, we prove the other part. Assume \(G\) is a simple, claw-free, paw-free graph which is connected. If \(G\) is a path or a cycle, then there is nothing to prove. Consider \(G\) being neither a path nor a cycle. Then \(\Delta\ge 3\). By Theorem 1, \(G\) is triangle-free or a complete multipartite graph. So, in this instance, \(G\) is a complete \(k\)-partite graph or else we obtain a claw as an induced sub-graph which is not allowed. Let \(V_1,V_2,\cdots,V_k\) be the partite sets of \(G\). Then \(|V_i|=1 \ \mbox{or} \ 2\) for all \(i: \ 1\le i\le k\), otherwise, we obtain a claw is a induced sub-graph of \(G\). Thus \(k\ge 3\) or else we get a path or a cycle which contradicts the assumption of this case. Moreover, \(\delta\ge n-2\), since \(G\) is complete multipartite and \(|V_i|\le 2\) for all \(i\). Hence, the maximum number of edges that can be deleted from the complete graph to obtain \(G\) cannot exceed \(\lfloor \frac{n}{2}\rfloor\), otherwise, we contradict \(\delta\). Likewise, only disjoint edges can be deleted from the complete graph. Thus \(G=K_n-tK_2\) for \(0\le t\le \lfloor \frac{n}{2}\rfloor\) as desired.
Note that if \(|V_i|=1\) for all \(i\), then \(G=K_n\) and if \(|V_i|=2\) for all \(i\), then \(G=K_n-\frac{n}{2}K_2\). To deduce properties \((a)\)–\((d)\). We realize that if \(G\) is neither a path nor a cycle, then \(G\notin {\cal G}_1 \cup {\cal G}_2\) for in this instance every graph in \({\cal G}_1\) has a paw as an induced sub-graph where as every graph in \({\cal G}_2\) has a claw as an induced sub-graph, see Theorem 2. Further, since \(\delta\ge n-2\), we have \(n\le \delta+2\le 2\delta\) whenever \(G\notin \lbrace P_n,C_n\rbrace\). Hence, if \(G\notin \lbrace P_n,C_n\rbrace\), then by Theorem 2, \(G\) is Hamiltonian-connected and Property \((a)\) holds. So, Property \((b)\) follows by an application of Theorem 3, since \(k\ge 3\) and \(G\) is complete \(k\)-partite graph. Properties \((c)\) and \((d)\) follows directly from the Implications 1 and the fact that a cycle is homogeneously traceable. Property \((e)\) follows from the fact that the graph \(K_n-tK_2\) has leaf number \(n-2\) or \(n-1\). That is, let \(v\in V(G)\) be such that \(\deg_G(v)=\Delta\) and for some fixed \(j\), let \(V_j\) be the partite set containing \(v\). If \(|V_j|=1\), then \(\deg_G(v)=n-1\), since \(G\) is complete multipartite. This in conjunction with \(\delta\ge n-2\) yield the result. ◻
The characterization of claw-free, paw-free graphs also filled the gap between a result by Olariu [1] and a result by Faudree and Gould [2] in that the note highlighted some properties of this class of graphs and subsequently yields standard results in the relevant literature.
We acknowledge suggestions by the reviewers which improved the initial version of this note.