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

      0 references
      0 references
      0 references
      21 February 1993
      0 references
      balanced graphs
      0 references
      binary labeling
      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

      Identifiers