On a product dimension of bipartite graphs (Q3312264)

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 3841901
Language Label Description Also known as
default for all languages
No label defined
    English
    On a product dimension of bipartite graphs
    scientific article; zbMATH DE number 3841901

      Statements

      On a product dimension of bipartite graphs (English)
      0 references
      0 references
      0 references
      0 references
      1983
      0 references
      induced subgraph
      0 references
      bipartite dimension
      0 references
      quotient graph
      0 references
      0 references
      0 references
      Let \(P_ m\) denote the path with m vertices. The third author has shown [Combinatorics, Keszthely 1976, Colloq. Math. Soc. János Bolyai 18, 805-820 (1978; Zbl 0392.05028)] ''that each bipartite graph G can be represented as an induced subgraph of \(P^ n_ 3\) with sufficiently large n. The minimum such n will be called the bipartite dimension of G, and denoted by bid G''. This product dimension is ''analogous to the Dushnik-Miller dimension of posets and to the dimension of general symmetric graphs''. Define an equivalence relation \(\sim\) on a graph G by \(x\sim y\) if and only if \([xz\in E(G)\Leftrightarrow yz \in E(G)]\); denote by \(M(G)\) the quotient graph \(G/\sim\). Theorem 1. If \(M(G)=G\), then \(\text{bid}G \leq frac{1}{2}| V(G)|\). In general, \(\text{bid}G\leq frac{1}{2}| V(G)| +1\). Theorem 2. The probability that a bipartite graph with \(| V(G)| = n\) has \(\text{bid}G > frac{1}{2}n - 2n^{\frac{1}{2}}\log n\) tends to 1 as \(n\) increases. The last section contains a number of ''concrete values and estimates'' of the bipartite dimension of discrete graphs, paths, even circuits, etc., and the following general theorem: Theorem 3. Let \(d\) be the maximum degree in \(G\); then \[ \text{bid}G \leq(d^2 - d + 1) \cdot \left[ \lceil frac{1}{2}\{\log | V(G)| + frac{1}{2}\log \log | V(G)| +3 \} \rceil + \lceil \log d \rceil \right] \] (where \(\lceil x\rceil\) denotes the ''upper integral approximation'' of \(x)\).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references