scientific article; zbMATH DE number 125598

From MaRDI portal
Publication:4027306





[For the entire collection see Zbl 0745.00025.] Let \(G\) be a graph with vertex set \(V\) and edge set \(E\). For a graph \(G\) a binary labeling \(f:V\to\{0,1\}\) divides the vertex set \(V\) into two parts \(V_ 0\) and \(V_ 1\), where \(V_ i\) is the set of vertices labeled \(i\). Let \(v_ i\) be the cardinality of \(V_ i\) and \(e_ i\) the number of edges of the subgraph induced by \(V_ i\) \((i=0,1)\). A graph is called balanced (strongly balanced) if there is a binary labeling \(f\) such that \(| v_ 0-v_ 1|\leq 1\) and \(| e_ 0-e_ 1|\leq 1\) \((v_ 0=v_ 1\) and \(e_ 0=e_ 1)\). This paper presents some classes of graphs which are balanced or strongly balanced: \(k\)- regular graphs with order \(p\) are strongly balanced if \(p\) is even, and balanced if \(p\) is odd and \(k=2\); a complete bipartite \(K_{m,n}\) is strongly balanced if \(m\) and \(n\) both are even; the Cartesian product \(G\times H\) and compositions \(G[H]\) and \(H[G]\) are strongly balanced for any \(H\) if \(G\) is strongly balanced.




Cited in
(30)








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 Q4027306)