# Questions tagged [degree-sequence]

The degree-sequence tag has no usage guidance.

**6**

votes

**2**answers

124 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 ...

**3**

votes

**0**answers

100 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 ...

**5**

votes

**1**answer

137 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)...

**3**

votes

**0**answers

95 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?
...

**4**

votes

**2**answers

201 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}\...

**2**

votes

**3**answers

240 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 ...

**8**

votes

**1**answer

693 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-...

**4**

votes

**1**answer

226 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 ...

**1**

vote

**1**answer

170 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 ...