scientific article; zbMATH DE number 125450

From MaRDI portal
Publication:4027149





[For the entire collection see Zbl 0748.00023.] All graphs considered in this paper are finite and simple. We follow the terminology of \textit{F. Harary} [Graph theory (1969; Zbl 0182.577)]. The order of a graph \(G\) is \(| V(G)|\) and its size \(| E(G)|\). If \(X\subseteq V(G)\) we denote by \(\Gamma(X)\) the set of vertices adjacent to vertices in \(X\) and by \(d(v)=|\Gamma(v)|\) the vertex degree of \(v\), and by \(\delta(G)\) the minimal vertex degree of a vertex of \(G\). For a given graph \(G\) let \(F_ G=\{X\subseteq V(G):X\neq\emptyset\) and \(\Gamma(X)\neq V(G)\}\). According to \textit{D. R. Woodall} [J. Comb. Theory, Ser. B 15, 225-255 (1973; Zbl 0253.05139)], the binding number of a graph \(G\), denoted by bind\((G)\), is defined by \(\text{bind}(G)=\min\{|\Gamma(X)|/| X|:X\in F_ G\}\). A set \(X\in F_ G\) is the realizing set for \(\text{bind}(G)\) if \(\text{bind}(G)=|\Gamma(X)|/| X|\). This paper is intended to survey and to complete the collection of main results, problems and papers for the binding number. We describe here also the structure of the realizing sets of the binding number.












This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4027149)