The binding number of line graphs and total graphs (Q1086594): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q5572939 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3922728 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3682521 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4724672 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The binding number of a graph and its Anderson number / rank | |||
Normal rank |
Revision as of 18:11, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The binding number of line graphs and total graphs |
scientific article |
Statements
The binding number of line graphs and total graphs (English)
0 references
1985
0 references
\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.
0 references
binding number
0 references
line graphs
0 references
total graphs
0 references