The binding number of line graphs and total graphs (Q1086594): Difference between revisions

\textit{D. R. Woodall} [J. Comb. Theory, Ser. B 15, 225-255 (1973; Zbl 0253.05139)] defined the binding number bind (G) of a graph G as min\(\{| \Gamma (X)| /| X|:\) \(X\subseteq V(G)\) such that \(X\neq \emptyset\) and \(\Gamma\) (X)\(\neq V(G)\}\) and proved that bind (G)\(\leq (n-1)/(n-\delta)\) where \(n=| V(G)|\) and \(\delta =\min imum\) degree of G. The authors define the graph families \({\mathcal G}_ 1=\{G|\) for every \(X\subseteq V(G)\), \(X\neq \emptyset\), \(\Gamma\) (X)\(\neq V(G)\) one has \(| \Gamma (X)| \geq | X| +\delta (G)=1\}\) and \({\mathcal G}_ 2=\{G|\) bind (G)\(=(n-1)/(n-\delta)\}\) and prove that \({\mathcal G}_ 1\varsubsetneq {\mathcal G}_ 2\). They further prove that the line graphs and total graphs of \(K_ n\), \(K_{m,n}\) and \(W_ n\) belong to the family \({\mathcal G}_ 1\) and thus easily determine the binding number of these graphs.