The number of labeled connected graphs modulo prime powers

Arun P. Mani; Rebecca J. Stones

doi:10.1137/15M1024615

The number of labeled connected graphs modulo prime powers

Arun P. Mani, Rebecca J. Stones

Research output: Contribution to journal › Article › Research › peer-review

2 Citations (Scopus)

Abstract

Let c_n denote the number of vertex-labeled connected graphs on n vertices. Using group actions and elementary number theory, we show that the infinite sequence, c_n : n ≥ 1, is ultimately periodic modulo every positive integer. We state and prove our results for sequences defined by a weighted generalization of cn and conjecture that these results are suggestive of similar periodic behavior of the Tutte polynomial evaluations of the complete graph Kn at integer points.

Original language	English
Pages (from-to)	1046-1057
Number of pages	12
Journal	SIAM Journal on Discrete Mathematics
Volume	30
Issue number	2
DOIs	https://doi.org/10.1137/15M1024615
Publication status	Published - 2016

Keywords

Connected graphs
Tutte polynomial

Access to Document

10.1137/15M1024615Licence: CC BY

117364062_oaFinal published version, 295 KB

Cite this

@article{d918b85bd3e84d2e8bf4c16097eed9de,

title = "The number of labeled connected graphs modulo prime powers",

abstract = "Let cn denote the number of vertex-labeled connected graphs on n vertices. Using group actions and elementary number theory, we show that the infinite sequence, cn : n ≥ 1, is ultimately periodic modulo every positive integer. We state and prove our results for sequences defined by a weighted generalization of cn and conjecture that these results are suggestive of similar periodic behavior of the Tutte polynomial evaluations of the complete graph Kn at integer points.",

keywords = "Connected graphs, Tutte polynomial",

author = "Mani, {Arun P.} and Stones, {Rebecca J.}",

year = "2016",

doi = "10.1137/15M1024615",

language = "English",

volume = "30",

pages = "1046--1057",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial & Applied Mathematics (SIAM)",

number = "2",

}

TY - JOUR

T1 - The number of labeled connected graphs modulo prime powers

AU - Mani, Arun P.

AU - Stones, Rebecca J.

PY - 2016

Y1 - 2016

N2 - Let cn denote the number of vertex-labeled connected graphs on n vertices. Using group actions and elementary number theory, we show that the infinite sequence, cn : n ≥ 1, is ultimately periodic modulo every positive integer. We state and prove our results for sequences defined by a weighted generalization of cn and conjecture that these results are suggestive of similar periodic behavior of the Tutte polynomial evaluations of the complete graph Kn at integer points.

AB - Let cn denote the number of vertex-labeled connected graphs on n vertices. Using group actions and elementary number theory, we show that the infinite sequence, cn : n ≥ 1, is ultimately periodic modulo every positive integer. We state and prove our results for sequences defined by a weighted generalization of cn and conjecture that these results are suggestive of similar periodic behavior of the Tutte polynomial evaluations of the complete graph Kn at integer points.

KW - Connected graphs

KW - Tutte polynomial

UR - http://www.scopus.com/inward/record.url?scp=84976863743&partnerID=8YFLogxK

U2 - 10.1137/15M1024615

DO - 10.1137/15M1024615

M3 - Article

AN - SCOPUS:84976863743

SN - 0895-4801

VL - 30

SP - 1046

EP - 1057

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

The number of labeled connected graphs modulo prime powers

Abstract

Keywords

Access to Document

Other files and links

Cite this