The binding number of line graphs and total graphs
type: Item
instance of: scholarly article
title: The binding number of line graphs and total graphs
zbMATH Open document ID: 0609.05061
DOI: 10.1007/BF02582963
author: Akira Saito
author: Songlin Tian
published in: Graphs and Combinatorics
publication date: 1985-01-01T00:00:00Z
review text: \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.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3985278
zbMATH Keywords: binding number
zbMATH Keywords: line graphs
zbMATH Keywords: total graphs
MaRDI profile type: Publication
cites work: Q5572939
cites work: Q3922728
cites work: Q3682521
cites work: Q4724672
cites work: The binding number of a graph and its Anderson number
full work available at URL: https://doi.org/10.1007/bf02582963
OpenAlex ID: W2048661464
Recommended article: Q5690315
Recommended article: Q4871088
Recommended article: Q3815351
Recommended article: Q4027149
Recommended article: Q3775589
Recommended article: Q4033285
Recommended article: Q4726285
Recommended article: Q4293776
Recommended article: Q3138227
Recommended article: Q3399443
description: scientific article; zbMATH DE number 3985278