No label defined (Q4027306)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 125598
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 125598 |
Statements
21 February 1993
0 references
balanced graphs
0 references
binary labeling
0 references
0.8575253486633301
0 references
0.8500310778617859
0 references
0.8480854630470276
0 references
[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.
0 references