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
1983
0 references
induced subgraph
0 references
bipartite dimension
0 references
quotient graph
0 references
0 references
0.7737796
0 references
0.7674252
0 references
0 references
0.74900454
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