검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Formulas for Counting the Numbers of Connected Spanning Subgraphs with at Most n+1 Edges in a Complete Graph Kn 최대로 연결된 스패닝 하위 그래프 수를 계산하는 공식 n완전한 그래프의 간선 +1 Kn

Peng CHENG, Shigeru MASUYAMA

  • 조회수

    0

  • 이것을 인용

요약 :

하자 Ni 연결된 스패닝 하위 그래프의 수 i(n-1 i m)의 가장자리 n-꼭지점 m-에지 무방향 그래프 G=(V,E). 이기는 하지만 Nn-1 행렬 트리 정리(Matrix-tree theorem)에 의해 다항식 시간으로 계산됩니다. Nn 그래프에 대해 효율적으로 계산됩니다. G 미해결 문제입니다(예: [2] 참조). 반면에, Nn2Nn-1Nn+1 그래프의 경우 G 로그 오목 추측의 일부로도 열려 있습니다(예: [6],[12] 참조). 본 논문에서는 완전한 그래프를 위해 Kn, 우리는에 대한 공식을 제공합니다 Nn, Nn+1, 이에 의해 Nn, Nn+1 다항식 시간으로 각각 계산됩니다. n, 특히 다음을 증명합니다. Nn2> Nn-1Nn+1 뿐만 아니라.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2314-2321
발행일
2008/09/01
공개일
온라인 ISSN
1745-1337
DOI
10.1093/ietfec/e91-a.9.2314
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주

작성자

키워드