Does a (complete) $\mathfrak{a}$-partite graph always have a maximum in AND out degree?

51 Views Asked by At

A graph $G$ is called $\mathfrak{a}$-partite (with $\mathfrak{a}$ being any non empty cardinal), if there exists a partition $\mathcal P$ of $V(G)$ such that any two vertices in the same class $A\in\mathcal P$ are not adjacent.

Here we call such a $\mathfrak{a}$-partite graph $G$ complete, if for any $A,B\in\mathcal P$ with $A\neq B$ and vertices $v\in A,w\in B$ there is at least one (directed) edge between $v$ and $w$ (that means from $v$ to $w$ or from $w$ to $v$, both directions not being necessarily required).

The in/out degree of a vertex $v$ is the cardinality of all edges that point into/out of $v$, lets denote it by $d^-(v)$ and $d^+(v)$ respectively. The (undirected) degree of $v$ is then defined as $d(v)=d^-(v)+d^+(v)$. We say that $G$ has a maximal in/out/undirected degree if there is a vertex $w$ with

  • $d^-(w)=\sup_{v\in V(G)}d^-(w)$,
  • $d^+(w)=\sup_{v\in V(G)}d^+(w)$ or
  • $d(w)=\sup_{v\in V(G)}d(w)$ respectively.

Question: In an $\mathfrak{a}$-partite graph $G$ (with $\mathfrak a<|V(G)|$), does $G$ having a maximal undirected degree imply that $G$ has a maximal in degree AND a maximal out degree? If no, how does the answer change if we limit ourselves to complete $\mathfrak{a}$-partite graphs, simple graphs (i.e. at most one edge from one vertex to another), $\mathfrak{a}\in\mathbb Z_+$ (i.e. only finite partitions, but with possibly infinite elements in each partition class) or any combination thereof?

Insight: It can be shown that if $G$ has a maximal degree, then it has a maximal in degree OR a maximal out degree. Also there are graphs where only one of the two possibilities holds.

For example, let us define the divisibility graph $D$ as such: The vertices are positive integers, so $V(D)=\mathbb Z_+$. The edges form a subset of $\mathbb Z_+\times\mathbb Z_+$, with $(k,n)\in E(D)$ going from $k$ to $n$ iff $k\mid n$. Now for any $m\in\mathbb Z_+$, since $m\mid \ell m$ for any $\ell\in\mathbb Z_+$, we have $d^+(m)=|\mathbb Z_+|=\omega$. Furthermore $k\mid m$ implies $k\leq m$, so $d^-(m)\leq m$ and $d(m)=\omega$. On the other hand, for any $\ell\in\mathbb Z_+$ we have $d^-\left(p_1\cdot\ldots\cdot p_\ell\right)=\ell+1$, where $p_i$ denotes the $i$-th prime. In conclusion, $D$ has a maximal degree and a maximal out degree, but not a maximal in degree.

I believe the answer to the question in the complete variant to be positive, but have no further proof yet. So far I only noted any graph is a $|V(G)|$-partite graph, and therefore $D$ above serves as a counterexample to the general question with $\mathfrak{a}=|V(G)|$, which is why I excluded that case.

1

There are 1 best solutions below

2
On BEST ANSWER

Consider a bipartite graph with nodes $(\{0\}\times\omega) \cup (\{1\}\times\omega_\omega)$ and an edge from $(0,n)$ to $(1,\alpha)$ if $\alpha<\omega_n$, and from $(1,\alpha)$ to $(0,n)$ otherwise.

This is complete in your sense, and has a maximal undirected degree, namely $\aleph_\omega$.

But the the outdegree of $(0,n)$ is $\aleph_n$, whereas the outdegree of $(1,\alpha)$ is always $\aleph_0$. So there is not a maximal outdegree.