학술
기타
The number of perfect matchings in 3-connected planar graphs
arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.Abstract
A graph is matchable if it admits a perfect matching.
Recently, Goedgebeur et al. asked whether there exists a constant $c<12$ such that infinitely many matchable planar $3$-connected graphs, each with exactly $c$ perfect matchings.
We prove that every matchable planar $3$-connected graphs on at least 40 vertices has at least 12 perfect matchings, and this lower bound is sharp.
This answers the question negatively.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요
관련 뉴스
관련 뉴스 제보는 로그인 후 가능합니다.
'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