Same eccentricity sequence in non-isomorphic graphs

Clash Royale CLAN TAG#URR8PPP

up vote
2
down vote

favorite

I want to find two connected, non-isomorphic graphs with order n with the same eccentricity sequence where $nge 4$.

The closest I could think of was $K_1,n$ having an eccentricity sequence of $1,2,2,2,2,2...,2$ and $K_n+1$ having an eccentricity sequence of $1,1,1,1,1,1,1....,1$. This yields eccentricity sequence being off by $1$ for $nge 4$.

Is there some methodical way of finding two non-isomorphic graphs with the same eccentricity sequence?

graph-theory

share|cite|improve this question

asked 4 hours ago

Corp. and Ltd.

14313

add a comment | 

up vote
2
down vote

favorite

I want to find two connected, non-isomorphic graphs with order n with the same eccentricity sequence where $nge 4$.

The closest I could think of was $K_1,n$ having an eccentricity sequence of $1,2,2,2,2,2...,2$ and $K_n+1$ having an eccentricity sequence of $1,1,1,1,1,1,1....,1$. This yields eccentricity sequence being off by $1$ for $nge 4$.

Is there some methodical way of finding two non-isomorphic graphs with the same eccentricity sequence?

graph-theory

share|cite|improve this question

asked 4 hours ago

Corp. and Ltd.

14313

add a comment | 

up vote
2
down vote

favorite

up vote
2
down vote

favorite

I want to find two connected, non-isomorphic graphs with order n with the same eccentricity sequence where $nge 4$.

The closest I could think of was $K_1,n$ having an eccentricity sequence of $1,2,2,2,2,2...,2$ and $K_n+1$ having an eccentricity sequence of $1,1,1,1,1,1,1....,1$. This yields eccentricity sequence being off by $1$ for $nge 4$.

Is there some methodical way of finding two non-isomorphic graphs with the same eccentricity sequence?

graph-theory

share|cite|improve this question

asked 4 hours ago

Corp. and Ltd.

14313

I want to find two connected, non-isomorphic graphs with order n with the same eccentricity sequence where $nge 4$.

The closest I could think of was $K_1,n$ having an eccentricity sequence of $1,2,2,2,2,2...,2$ and $K_n+1$ having an eccentricity sequence of $1,1,1,1,1,1,1....,1$. This yields eccentricity sequence being off by $1$ for $nge 4$.

Is there some methodical way of finding two non-isomorphic graphs with the same eccentricity sequence?

graph-theory

graph-theory

share|cite|improve this question

asked 4 hours ago

Corp. and Ltd.

14313

share|cite|improve this question

asked 4 hours ago

Corp. and Ltd.

14313

share|cite|improve this question

share|cite|improve this question

asked 4 hours ago

Corp. and Ltd.

14313

asked 4 hours ago

Corp. and Ltd.

14313

asked 4 hours ago

Corp. and Ltd.

14313

14313

add a comment | 

add a comment | 

2 Answers
2

active

oldest

votes

up vote
3
down vote



accepted

Try $K_1,n$ and $K_1,n+e$ (add one more edge to $K_1,n$) where $nge3$.

share|cite|improve this answer

answered 3 hours ago

bof

47.1k349114

add a comment | 

up vote
2
down vote

A reasonably "methodical" way to find such examples is to use Mathematica. (Other software might do as well.)

First, we get a list of all "notable" connected graphs on 5 vertices (for order 5, all graphs happen to be notable, but if we tried this for a larger order, we'd miss some). The syntax here is a bit awkward: GraphData[5] gives Mathematica's names for all these graphs, and then applying GraphData again to those names gives the actual graphs. If 5 hadn't been enough vertices, we could have tried 6 or more.

graphs = Select[GraphData /@ GraphData[5], ConnectedGraphQ];

Then, we group the graphs into classes with the same eccentricity sequence. (Actually, EccentricityCentrality computes the reciprocals of the eccentricities within a connected component, but that's fine.)

classes = GatherBy[graphs, Sort @* EccentricityCentrality];

The largest of the classes, produced by

MaximalBy[classes, Length]

gives the following output:

All of these graphs have the same eccentricity sequence $1,2,2,2,2$.

share|cite|improve this answer

answered 2 hours ago

Misha Lavrov

38.7k55196

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Of course, once we find these examples, we can think about why they work and realize it's basically the same principle as in bof's answer.
  – Misha Lavrov
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just found the unique example on $4$ vertices (using wetware instead of Mathematica) and generalized it.
  – bof
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There's also a large family of examples with eccentricity sequence $2,2,dots,2$. (For example, any $K_m,n$ with $m,nge 2$ has this eccentricity sequence; we can also obtain it by taking literally any graph on $n$ vertices where all vertex degrees are strictly between $frac n2$ and $n-1$.)
  – Misha Lavrov
  1 hour ago
  

  
  
  
  

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%2f2937485%2fsame-eccentricity-sequence-in-non-isomorphic-graphs%23new-answer', 'question_page');

);

Post as a guest

Name Email

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
3
down vote



accepted

Try $K_1,n$ and $K_1,n+e$ (add one more edge to $K_1,n$) where $nge3$.

share|cite|improve this answer

answered 3 hours ago

bof

47.1k349114

add a comment | 

up vote
3
down vote



accepted

Try $K_1,n$ and $K_1,n+e$ (add one more edge to $K_1,n$) where $nge3$.

share|cite|improve this answer

answered 3 hours ago

bof

47.1k349114

add a comment | 

up vote
3
down vote



accepted

up vote
3
down vote



accepted

Try $K_1,n$ and $K_1,n+e$ (add one more edge to $K_1,n$) where $nge3$.

share|cite|improve this answer

answered 3 hours ago

bof

47.1k349114

Try $K_1,n$ and $K_1,n+e$ (add one more edge to $K_1,n$) where $nge3$.

share|cite|improve this answer

answered 3 hours ago

bof

47.1k349114

share|cite|improve this answer

share|cite|improve this answer

answered 3 hours ago

bof

47.1k349114

answered 3 hours ago

bof

47.1k349114

answered 3 hours ago

bof

47.1k349114

47.1k349114

add a comment | 

add a comment | 

up vote
2
down vote

A reasonably "methodical" way to find such examples is to use Mathematica. (Other software might do as well.)

First, we get a list of all "notable" connected graphs on 5 vertices (for order 5, all graphs happen to be notable, but if we tried this for a larger order, we'd miss some). The syntax here is a bit awkward: GraphData[5] gives Mathematica's names for all these graphs, and then applying GraphData again to those names gives the actual graphs. If 5 hadn't been enough vertices, we could have tried 6 or more.

graphs = Select[GraphData /@ GraphData[5], ConnectedGraphQ];

Then, we group the graphs into classes with the same eccentricity sequence. (Actually, EccentricityCentrality computes the reciprocals of the eccentricities within a connected component, but that's fine.)

classes = GatherBy[graphs, Sort @* EccentricityCentrality];

The largest of the classes, produced by

MaximalBy[classes, Length]

gives the following output:

All of these graphs have the same eccentricity sequence $1,2,2,2,2$.

share|cite|improve this answer

answered 2 hours ago

Misha Lavrov

38.7k55196

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Of course, once we find these examples, we can think about why they work and realize it's basically the same principle as in bof's answer.
  – Misha Lavrov
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just found the unique example on $4$ vertices (using wetware instead of Mathematica) and generalized it.
  – bof
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There's also a large family of examples with eccentricity sequence $2,2,dots,2$. (For example, any $K_m,n$ with $m,nge 2$ has this eccentricity sequence; we can also obtain it by taking literally any graph on $n$ vertices where all vertex degrees are strictly between $frac n2$ and $n-1$.)
  – Misha Lavrov
  1 hour ago
  

  
  
  
  

add a comment | 

up vote
2
down vote

A reasonably "methodical" way to find such examples is to use Mathematica. (Other software might do as well.)

First, we get a list of all "notable" connected graphs on 5 vertices (for order 5, all graphs happen to be notable, but if we tried this for a larger order, we'd miss some). The syntax here is a bit awkward: GraphData[5] gives Mathematica's names for all these graphs, and then applying GraphData again to those names gives the actual graphs. If 5 hadn't been enough vertices, we could have tried 6 or more.

graphs = Select[GraphData /@ GraphData[5], ConnectedGraphQ];

Then, we group the graphs into classes with the same eccentricity sequence. (Actually, EccentricityCentrality computes the reciprocals of the eccentricities within a connected component, but that's fine.)

classes = GatherBy[graphs, Sort @* EccentricityCentrality];

The largest of the classes, produced by

MaximalBy[classes, Length]

gives the following output:

All of these graphs have the same eccentricity sequence $1,2,2,2,2$.

share|cite|improve this answer

answered 2 hours ago

Misha Lavrov

38.7k55196

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Of course, once we find these examples, we can think about why they work and realize it's basically the same principle as in bof's answer.
  – Misha Lavrov
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just found the unique example on $4$ vertices (using wetware instead of Mathematica) and generalized it.
  – bof
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There's also a large family of examples with eccentricity sequence $2,2,dots,2$. (For example, any $K_m,n$ with $m,nge 2$ has this eccentricity sequence; we can also obtain it by taking literally any graph on $n$ vertices where all vertex degrees are strictly between $frac n2$ and $n-1$.)
  – Misha Lavrov
  1 hour ago
  

  
  
  
  

add a comment | 

up vote
2
down vote

up vote
2
down vote

A reasonably "methodical" way to find such examples is to use Mathematica. (Other software might do as well.)

First, we get a list of all "notable" connected graphs on 5 vertices (for order 5, all graphs happen to be notable, but if we tried this for a larger order, we'd miss some). The syntax here is a bit awkward: GraphData[5] gives Mathematica's names for all these graphs, and then applying GraphData again to those names gives the actual graphs. If 5 hadn't been enough vertices, we could have tried 6 or more.

graphs = Select[GraphData /@ GraphData[5], ConnectedGraphQ];

Then, we group the graphs into classes with the same eccentricity sequence. (Actually, EccentricityCentrality computes the reciprocals of the eccentricities within a connected component, but that's fine.)

classes = GatherBy[graphs, Sort @* EccentricityCentrality];

The largest of the classes, produced by

MaximalBy[classes, Length]

gives the following output:

All of these graphs have the same eccentricity sequence $1,2,2,2,2$.

share|cite|improve this answer

answered 2 hours ago

Misha Lavrov

38.7k55196

A reasonably "methodical" way to find such examples is to use Mathematica. (Other software might do as well.)

First, we get a list of all "notable" connected graphs on 5 vertices (for order 5, all graphs happen to be notable, but if we tried this for a larger order, we'd miss some). The syntax here is a bit awkward: GraphData[5] gives Mathematica's names for all these graphs, and then applying GraphData again to those names gives the actual graphs. If 5 hadn't been enough vertices, we could have tried 6 or more.

graphs = Select[GraphData /@ GraphData[5], ConnectedGraphQ];

Then, we group the graphs into classes with the same eccentricity sequence. (Actually, EccentricityCentrality computes the reciprocals of the eccentricities within a connected component, but that's fine.)

classes = GatherBy[graphs, Sort @* EccentricityCentrality];

The largest of the classes, produced by

MaximalBy[classes, Length]

gives the following output:

All of these graphs have the same eccentricity sequence $1,2,2,2,2$.

share|cite|improve this answer

answered 2 hours ago

Misha Lavrov

38.7k55196

share|cite|improve this answer

share|cite|improve this answer

answered 2 hours ago

Misha Lavrov

38.7k55196

answered 2 hours ago

Misha Lavrov

38.7k55196

answered 2 hours ago

Misha Lavrov

38.7k55196

38.7k55196

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Of course, once we find these examples, we can think about why they work and realize it's basically the same principle as in bof's answer.
  – Misha Lavrov
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just found the unique example on $4$ vertices (using wetware instead of Mathematica) and generalized it.
  – bof
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There's also a large family of examples with eccentricity sequence $2,2,dots,2$. (For example, any $K_m,n$ with $m,nge 2$ has this eccentricity sequence; we can also obtain it by taking literally any graph on $n$ vertices where all vertex degrees are strictly between $frac n2$ and $n-1$.)
  – Misha Lavrov
  1 hour ago
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Of course, once we find these examples, we can think about why they work and realize it's basically the same principle as in bof's answer.
  – Misha Lavrov
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I just found the unique example on $4$ vertices (using wetware instead of Mathematica) and generalized it.
  – bof
  2 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There's also a large family of examples with eccentricity sequence $2,2,dots,2$. (For example, any $K_m,n$ with $m,nge 2$ has this eccentricity sequence; we can also obtain it by taking literally any graph on $n$ vertices where all vertex degrees are strictly between $frac n2$ and $n-1$.)
  – Misha Lavrov
  1 hour ago
  

  
  
  
  

Of course, once we find these examples, we can think about why they work and realize it's basically the same principle as in bof's answer.
– Misha Lavrov
2 hours ago

Of course, once we find these examples, we can think about why they work and realize it's basically the same principle as in bof's answer.
– Misha Lavrov
2 hours ago

I just found the unique example on $4$ vertices (using wetware instead of Mathematica) and generalized it.
– bof
2 hours ago

I just found the unique example on $4$ vertices (using wetware instead of Mathematica) and generalized it.
– bof
2 hours ago

There's also a large family of examples with eccentricity sequence $2,2,dots,2$. (For example, any $K_m,n$ with $m,nge 2$ has this eccentricity sequence; we can also obtain it by taking literally any graph on $n$ vertices where all vertex degrees are strictly between $frac n2$ and $n-1$.)
– Misha Lavrov
1 hour ago

There's also a large family of examples with eccentricity sequence $2,2,dots,2$. (For example, any $K_m,n$ with $m,nge 2$ has this eccentricity sequence; we can also obtain it by taking literally any graph on $n$ vertices where all vertex degrees are strictly between $frac n2$ and $n-1$.)
– Misha Lavrov
1 hour ago

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%2f2937485%2fsame-eccentricity-sequence-in-non-isomorphic-graphs%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