학술
기타
Irregular subgraph in a regular graph
arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.Abstract
A conjecture of Alon and Wei states that, for any $d$-regular graph $G$ with $n$ vertices, there exists a spanning subgraph $H$ such that for all $0\le i\le d$, we have $m(H, i)$, the number of vertices in $H$ with degree $i$, is between $\frac{n}{d+1}-2$ and $\frac{n}{d+1}+2$. We prove the conjecture for all fixed $d$ when $n$ is sufficiently large. More precisely, if $q=(q_0,\ldots,q_d)$ satisfies $$
\sum_{i=0}^d q_i=n,\qquad
\sum_{i=0}^d i q_i\equiv 0\pmod 2,\qquad
\left|q_i-\frac{n}{d+1}\right|\le 1
\quad (0\le i\le d), $$ then there is a spanning subgraph $H\subseteq G$ such that $$
m(H,i)=q_i
\qquad (0\le i\le d). $$
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요
관련 뉴스
관련 뉴스 제보는 로그인 후 가능합니다.