Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.research

Topic: Combinatorial problem on subgraphs of the Johnson graph
Replies: 0  

Advanced Search

Back to Topic List Back to Topic List  
Rodolfo Conde

Posts: 16
Registered: 3/24/10
Combinatorial problem on subgraphs of the Johnson graph
Posted: Sep 20, 2012 6:00 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Let $1\leqslant m \leqslant n$, $N=\{ 1,\ldots,n\}$. The Johnson graph
$J_{n,m}$ has as vertex set all subsets of $N$ of cardinality $m$, two
vertices $b_1,b_2$ are adjacent if and only if $\lvert b_1 \cap b_2 \rvert =
m - 1$. Let $V_{n,m}=V(J_{n,m})$. If $U\subset V_{n,m}$, define the set
$\zeta(U)$
as

$\zeta(U)= \{ c\cup d \mid c,d \in U \wedge \lvert c \cap d \rvert = m - 1
\}$.

Notice that each $f\in \zeta(U)$ has size $m+1$, because, if $f= c\cup d$
for $c,d \in U$, then
$\lvert c \rvert = \lvert d \rvert = m$ and it is known that $\lvert c \cap
d \rvert = m - 1
\Leftrightarrow \lvert c \cup d \rvert = m + 1$. Thus $\zeta(U)\subseteq
V_{n,m+1}$.

The problem: Suppose that $U\subset 2^N$ is a collection of subsets of $N$,
all of them of size m. Assume also that $\lvert U \rvert \leqslant n - m$
and that the subgraph $G\left[ U \right]$ of $J_{n,m}$ induced by $U$ is
disconnected.

Then prove that $\bigcup_{b\in \zeta(U)}b \neq N \vee G\left[ \zeta(U)
\right]$ is a disconnected subgraph of $J_{n,m+1}$.

The hard part of the proof, in which i have been unsuccessful, is when we
suppose that $\bigcup_{b\in \zeta(U)}b = N$, we have to show that $G\left[
\zeta(U) \right]$ is disconnected.

Can anyone shed some light on this matter ? Any hints or references ?

Thanks a lot for all your comments !!!

Greetings...




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.