학술
기타
Towards a strengthening of the second neighborhood conjecture
arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.Abstract
A longstanding conjecture of Seymour, called Seymour's second neighborhood conjecture, states that every oriented graph $D$ contains a vertex $x$ with $|N^{++}_D(x)|\geq |N^{+}_D(x)|$.
The conjecture was verified in a few special classes of oriented graphs, and it remains open for general oriented graphs.
We propose a stronger version of the conjecture that every oriented graph $D$ contains a vertex $x$ such that there exists a complete matching from $N^+_D(x)$ to $N^{++}_D(x)$.
We prove that this stronger version holds for every oriented graph with minimum out-degree at most $5$, and also for every $5$-anti-transitive oriented graph.
This implies that every oriented planar graph satisfies the stronger version.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요
관련 뉴스
관련 뉴스 제보는 로그인 후 가능합니다.
'research' 카테고리 뉴스
arXiv의 다른 기사
Deterministic Replay for AI Agent Systems
arXiv CS.AI
Generative Ontology Induction: Domain-Agnostic Schema Discovery from Document Corpora Using Large Language Models
arXiv CS.AI
Democratizing AI with Small Language Models: Structured Benchmarking and Parameter-Efficient Fine-Tuning for Local Deployment
arXiv CS.AI