Graphs with a given number of spanning trees

Clash Royale CLAN TAG#URR8PPP

up vote
4
down vote

favorite

Fix a natural number $n$. Then a tree on $n$ vertices has $1=n^0$ spanning tree, a cycle on $n$ spanning vertices has $n = n^1$ spanning trees, and the complete graph on $n$ vertices has $n^n-2$ spanning trees. These are the extremal trivial cases for what I am considering. Namely, for what natural $1leq k leq n-2$ does there exist a graph on $n$ vertices with $n^k$ spanning trees? And if yes, what does the graph look like (in the sense of some sort of characterization)?

I am mainly interested for $n=p$ being an odd prime and $p^p-3$ spanning trees. But any known results/approaches would be helpful.

As an aside, it is not difficult to find a graph with $p = 2k+1$ vertices and $p^k$ spanning trees. This is the only non-trivial case that I could figure out.

graph-theory

share|cite|improve this question

edited Jul 23 at 21:22

amWhy

189k25219431

asked Jul 23 at 21:20

xhimi

211

add a comment | 

up vote
4
down vote

favorite

Fix a natural number $n$. Then a tree on $n$ vertices has $1=n^0$ spanning tree, a cycle on $n$ spanning vertices has $n = n^1$ spanning trees, and the complete graph on $n$ vertices has $n^n-2$ spanning trees. These are the extremal trivial cases for what I am considering. Namely, for what natural $1leq k leq n-2$ does there exist a graph on $n$ vertices with $n^k$ spanning trees? And if yes, what does the graph look like (in the sense of some sort of characterization)?

I am mainly interested for $n=p$ being an odd prime and $p^p-3$ spanning trees. But any known results/approaches would be helpful.

As an aside, it is not difficult to find a graph with $p = 2k+1$ vertices and $p^k$ spanning trees. This is the only non-trivial case that I could figure out.

graph-theory

share|cite|improve this question

edited Jul 23 at 21:22

amWhy

189k25219431

asked Jul 23 at 21:20

xhimi

211

add a comment | 

up vote
4
down vote

favorite

up vote
4
down vote

favorite

Fix a natural number $n$. Then a tree on $n$ vertices has $1=n^0$ spanning tree, a cycle on $n$ spanning vertices has $n = n^1$ spanning trees, and the complete graph on $n$ vertices has $n^n-2$ spanning trees. These are the extremal trivial cases for what I am considering. Namely, for what natural $1leq k leq n-2$ does there exist a graph on $n$ vertices with $n^k$ spanning trees? And if yes, what does the graph look like (in the sense of some sort of characterization)?

I am mainly interested for $n=p$ being an odd prime and $p^p-3$ spanning trees. But any known results/approaches would be helpful.

As an aside, it is not difficult to find a graph with $p = 2k+1$ vertices and $p^k$ spanning trees. This is the only non-trivial case that I could figure out.

graph-theory

share|cite|improve this question

edited Jul 23 at 21:22

amWhy

189k25219431

asked Jul 23 at 21:20

xhimi

211

Fix a natural number $n$. Then a tree on $n$ vertices has $1=n^0$ spanning tree, a cycle on $n$ spanning vertices has $n = n^1$ spanning trees, and the complete graph on $n$ vertices has $n^n-2$ spanning trees. These are the extremal trivial cases for what I am considering. Namely, for what natural $1leq k leq n-2$ does there exist a graph on $n$ vertices with $n^k$ spanning trees? And if yes, what does the graph look like (in the sense of some sort of characterization)?

I am mainly interested for $n=p$ being an odd prime and $p^p-3$ spanning trees. But any known results/approaches would be helpful.

As an aside, it is not difficult to find a graph with $p = 2k+1$ vertices and $p^k$ spanning trees. This is the only non-trivial case that I could figure out.

graph-theory

share|cite|improve this question

edited Jul 23 at 21:22

amWhy

189k25219431

asked Jul 23 at 21:20

xhimi

211

share|cite|improve this question

share|cite|improve this question

edited Jul 23 at 21:22

amWhy

189k25219431

edited Jul 23 at 21:22

amWhy

189k25219431

edited Jul 23 at 21:22

amWhy

189k25219431

189k25219431

asked Jul 23 at 21:20

xhimi

211

asked Jul 23 at 21:20

xhimi

211

asked Jul 23 at 21:20

xhimi

211

211

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
2
down vote

For $k=1$, use a cycle graph.

Here are solutions for $kin(2,3,4,5,9,24)$. At the top is $v^k$ as the count of spanning trees, with $v$ as the vertex count.

The Petersen graph spanning tree count is $2times 10^3$.

The Chang graphs spanning tree count is $2 times 28^19$.

The Tietze graph spanning tree count is $5 times 12^3$.

The Gen Quadrangle(2,2) graph spanning tree count is $frac15^83$.

Here are solutions for $k in (frac83, frac103, frac174, frac254, frac314, frac354,frac212, frac1125, frac1163)$.

Here are a few graphs with $(p-2) p^p-3$ spanning trees.

The Paley graphs have $fracn-14^fracn-12 times n^fracn-32$ spanning trees.

share|cite|improve this answer

edited Jul 25 at 21:38

answered Jul 25 at 20:03

Ed Pegg

9,15932486

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860790%2fgraphs-with-a-given-number-of-spanning-trees%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
2
down vote

For $k=1$, use a cycle graph.

Here are solutions for $kin(2,3,4,5,9,24)$. At the top is $v^k$ as the count of spanning trees, with $v$ as the vertex count.

The Petersen graph spanning tree count is $2times 10^3$.

The Chang graphs spanning tree count is $2 times 28^19$.

The Tietze graph spanning tree count is $5 times 12^3$.

The Gen Quadrangle(2,2) graph spanning tree count is $frac15^83$.

Here are solutions for $k in (frac83, frac103, frac174, frac254, frac314, frac354,frac212, frac1125, frac1163)$.

Here are a few graphs with $(p-2) p^p-3$ spanning trees.

The Paley graphs have $fracn-14^fracn-12 times n^fracn-32$ spanning trees.

share|cite|improve this answer

edited Jul 25 at 21:38

answered Jul 25 at 20:03

Ed Pegg

9,15932486

add a comment | 

up vote
2
down vote

For $k=1$, use a cycle graph.

Here are solutions for $kin(2,3,4,5,9,24)$. At the top is $v^k$ as the count of spanning trees, with $v$ as the vertex count.

The Petersen graph spanning tree count is $2times 10^3$.

The Chang graphs spanning tree count is $2 times 28^19$.

The Tietze graph spanning tree count is $5 times 12^3$.

The Gen Quadrangle(2,2) graph spanning tree count is $frac15^83$.

Here are solutions for $k in (frac83, frac103, frac174, frac254, frac314, frac354,frac212, frac1125, frac1163)$.

Here are a few graphs with $(p-2) p^p-3$ spanning trees.

The Paley graphs have $fracn-14^fracn-12 times n^fracn-32$ spanning trees.

share|cite|improve this answer

edited Jul 25 at 21:38

answered Jul 25 at 20:03

Ed Pegg

9,15932486

add a comment | 

up vote
2
down vote

up vote
2
down vote

For $k=1$, use a cycle graph.

Here are solutions for $kin(2,3,4,5,9,24)$. At the top is $v^k$ as the count of spanning trees, with $v$ as the vertex count.

The Petersen graph spanning tree count is $2times 10^3$.

The Chang graphs spanning tree count is $2 times 28^19$.

The Tietze graph spanning tree count is $5 times 12^3$.

The Gen Quadrangle(2,2) graph spanning tree count is $frac15^83$.

Here are solutions for $k in (frac83, frac103, frac174, frac254, frac314, frac354,frac212, frac1125, frac1163)$.

Here are a few graphs with $(p-2) p^p-3$ spanning trees.

The Paley graphs have $fracn-14^fracn-12 times n^fracn-32$ spanning trees.

share|cite|improve this answer

edited Jul 25 at 21:38

answered Jul 25 at 20:03

Ed Pegg

9,15932486

For $k=1$, use a cycle graph.

Here are solutions for $kin(2,3,4,5,9,24)$. At the top is $v^k$ as the count of spanning trees, with $v$ as the vertex count.

The Petersen graph spanning tree count is $2times 10^3$.

The Chang graphs spanning tree count is $2 times 28^19$.

The Tietze graph spanning tree count is $5 times 12^3$.

The Gen Quadrangle(2,2) graph spanning tree count is $frac15^83$.

Here are solutions for $k in (frac83, frac103, frac174, frac254, frac314, frac354,frac212, frac1125, frac1163)$.

Here are a few graphs with $(p-2) p^p-3$ spanning trees.

The Paley graphs have $fracn-14^fracn-12 times n^fracn-32$ spanning trees.

share|cite|improve this answer

edited Jul 25 at 21:38

answered Jul 25 at 20:03

Ed Pegg

9,15932486

share|cite|improve this answer

share|cite|improve this answer

edited Jul 25 at 21:38

edited Jul 25 at 21:38

edited Jul 25 at 21:38

answered Jul 25 at 20:03

Ed Pegg

9,15932486

answered Jul 25 at 20:03

Ed Pegg

9,15932486

answered Jul 25 at 20:03

Ed Pegg

9,15932486

9,15932486

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860790%2fgraphs-with-a-given-number-of-spanning-trees%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email