Questions tagged [degree-sequence]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
10 votes
1 answer
614 views

Is there a program implementation for generating all non-isomorphic graphs with a given degree sequence?

I know the following problem is famous: For a given degree sequence $L$ that is graphic, find an (efficient) algorithm to generate all of the nonisomorphic realizations of $L$. This algorithm is ...
L.C. Zhang's user avatar
  • 1,605
0 votes
0 answers
55 views

Degree-constraints for the existence of vertex-disjoint directed cycle covers in digraphs

Given a digraph $G(E,V): (u,v)\in E\implies(v,u)\notin E$, what is known about lower bounds on the indegree and outdegree of the vertices that guarantee the existence of a vertex-disjoint directed ...
Manfred Weis's user avatar
  • 12.6k
3 votes
0 answers
75 views

Random graphs with prescibed degrees and triangles

In short: a random graph model generates (multi-)graphs with prescribed number of edges and minimal number of triangles for each vertex. Questions arise about the actual number of triangles and the ...
Matthieu Latapy's user avatar
6 votes
0 answers
125 views

Minimum of sums over degree products in a directed acyclic graph

My problem is the following: we have a graph $ G=(V,E)$. Having a total ordering $ \eta $ of the nodes, we give a direction to the edges such that $ (u,v) $ is directed from $u$ to $v$ iif $ \eta(u) &...
Alt-Tab's user avatar
  • 139
2 votes
0 answers
69 views

Are two degree sequences compatible, for random simple graph generation?

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$. Assume these degree sequences are graphical: there exist simple graphs (no ...
Matthieu Latapy's user avatar
5 votes
3 answers
394 views

Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$. Assume these degree sequences are graphical: there exist simple graphs (no ...
Matthieu Latapy's user avatar
3 votes
1 answer
136 views

Degree sequences after vertex removals

Consider a graph $G=(V, E)$ with $|V|=n$ vertices. Let $(v_1, \dots, v_n)$ be an ordered list of its vertices. Let $G_i=G[\{v_{i+1}, \dots, v_n\}]$ be the induced subgraph on the last $n-i$ vertices. ...
Jimmy's user avatar
  • 545
10 votes
4 answers
476 views

When is a large graph with a given degree sequence likely to be connected?

Are there any results on whether a large random graph with a given degree distribution is likely to be connected? In Erdős-Rényi graphs with $n$ vertices and $m$ edges, we have two sudden transitions ...
Szabolcs Horvát's user avatar
8 votes
1 answer
640 views

Construct a non-connected graph with a given degree sequence

Is there a known (efficient) algorithm to construct a non-connected graph with a given degree sequence (if it exists)? Examples The sequence $\{3, 2, 2, 2, 2, 2, 1\}$ has both connected and non-...
Szabolcs Horvát's user avatar
6 votes
2 answers
147 views

Eberhard-type theorems for Fisk triangulations?

A triangulation of a surface is called a Fisk triangulation if the degree of all but two vertices is even, and these two exceptional vertices of odd degree are neighbors. I would like to know what ...
domotorp's user avatar
  • 18.3k
3 votes
0 answers
118 views

Irregularly Intertwined Linear Recursions: Other References?

I was wondering if anyone had run across the following notion of intertwined linear recursions. I'm looking for references, or even a standard name. (I know one source, which is the genesis of this ...
Joe Silverman's user avatar
5 votes
1 answer
203 views

A simple requirement for a degree sequence to be graphical

The following theorem about the degree sequences of finite simple graphs is quite easy to prove from the Erdos-Gallai theorem. Let $0 \lt \alpha \le \beta \lt n$ be integers. Call $(\alpha,\beta,n)...
Brendan McKay's user avatar
3 votes
0 answers
109 views

Is there a Havel-Hakimi for geometric graphs?

Suppose that we are given $n$ points in the plane, with a degree prescribed for each, and the question is whether we can place a geometric graph on them. Is there an efficient algorithm for this? ...
domotorp's user avatar
  • 18.3k
5 votes
2 answers
232 views

Volume of the convex hull of the set of all graphic sequences of a given length

Consider the set of all graphic sequences with $n$ elements as a subset of $\mathbb{R}^{n}$, namely let $$D(n)=\{(d_{1},\dots,d_{n})\in\mathbb{Z}_{+}^{n}:d_{1}\geq\dots\geq d_{n},\ \sum_{i=1}^{n}d_{i}\...
Sergiy Kozerenko's user avatar
2 votes
3 answers
279 views

Making integer multisets graphic

Let $M=(X,f)$ be a multiset, where $X$ is the underlying set of elements and $f:X\rightarrow\mathbb{N}$ is the multiplicity function. For every $k\in\mathbb{N}$ put $k\cdot M:=(X,k\cdot f)$. It is ...
Sergiy Kozerenko's user avatar
9 votes
1 answer
1k views

Smallest Connected Graph for Given Degree Sequence

For a given integer sequence $(d_1, d_2,...,d_n)$, a natural question is if such a sequence is graphical, i.e. is a degree sequence of some graph. According to Erdős–Gallai theorem, A sequence of non-...
user avatar
6 votes
1 answer
692 views

Enumeration of graphs with a given and bounded degree sequence

What is the best known asymptotic formula for the number of graphs with a given degree sequence $(d_1, ... ,d_n)$, when the degrees are bounded by a constant and the number of vertices $n$ goes to ...
Zur Luria's user avatar
  • 1,613
5 votes
1 answer
288 views

Graphs with constant edge imbalance

The imbalance of an edge $(u,v) \in E(G)$ of a graph $G$ is defined as $|d(u)-d(v)|$ ($d$ being, as usual the degree). (This concept was introduced by Albertson in 1997) I'm interested in the set of ...
Felix Goldberg's user avatar
1 vote
1 answer
179 views

Have you come across this kind of "degree" concept?

Let $A \subseteq V(G)$ be a set of vertices in a graph $G$ and let $v \in V(G)$ be some vertex. Define $d_{A}(v)$ as the number of neighbours of $v$ inside $A$. Now suppose you have a graph whose ...
Felix Goldberg's user avatar