Suppose $N$ nodes with degree $v_1,v_2,...,v_n$ are given. How many distinct graphs can be built?

Have all these graphs the same property? I mean they all have the same shortest TSP, They are all planner or non-planner, They all have the same diagonal and any other property of a graph.

In the aggregate I would like to know, When there is a list of nodes degree, Is there any difference in terms of graph properties among all the graphs that can be generated using the nodes degree?

To be not too broad, what properties are the same among the graphs?

Thanks in advance.

  • $\begingroup$ this question asks for a lot of stuff but shows very little effort. $\endgroup$ – HereToRelax Jan 2 '17 at 18:53

Very different graphs can have the same degree sequence; here is a simple example.

Consider graphs with $12$ vertices, each of degree $2$. Such graphs are unions of cycles. It can have $1,2,3$, or $4$ components. Its clique number can be $2$ or $3$. The independence number can be $6$ (e.g., if the graph is $C_{12}$), $5$ (if the graph is $2$ copies of $C_3$ and one of $C_6$), or $4$ (if the graph is $4$ copies of $C_3$). Its chromatic number can be $2$ (e.g., for $C_{12}$) or $3$ (if it has an odd component). It can be bipartite (if all of its components are even) or not (if it has an odd component).

  • $\begingroup$ So generally, with a given list of nodes degree, the graphs are not Isomorphisms, right? $\endgroup$ – M a m a D Jan 2 '17 at 20:43
  • $\begingroup$ @Drupalist: Correct: a given degree sequence can correspond to non-isomorphic graphs. $\endgroup$ – Brian M. Scott Jan 2 '17 at 20:46
  • 1
    $\begingroup$ @Drupalist also consider for example the possibilities for connected 3-regular (cubic) graphs with 10 nodes. Loads of structural variety. $\endgroup$ – Joffan Jan 4 '17 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.