<p>1) Suppose we are given the following facts about a graph. What can we conclude/compute beyond these facts?</p>

<ul>
<li><p>The fact that graph $G(V,E)$ is planar, and thus that it is 4-colorable,</p></li>
<li><p>The degree of each vertex, and </p></li>
<li><p>The number of paths of length $j$ in the graph for all $j \in \{1,...,n\}$.</p></li>
</ul>

<p>Keep in mind that graph is not given (so in particular the neighbors of each vertex are not known).</p>

<p>2) What computations can be performed on a graph given in this manner that are more efficient than the corresponding computations on a general graph?</p>

<p>Thanks!</p>

CC BY-SA 3.0
2017-03-07T13:20:20.477Z
There is a lot of work on graphs with a given degree sequence, at least as far back as the Erdős-Gallai theorem.  Path sequences have been less studied, perhaps just limited to a 2015 paper by Bakalarski and Zygadło.  I'm not aware of any work that combines both degree and path sequences.
András Salamon
CC BY-SA 3.0
2017-03-11T08:11:02.110Z
One of these things is not like the others. "The fact that the graph is planar" is something that constrains the graph, and might lead to algorithms more efficient than for arbitrary graphs. "The degree of each vertex" is a piece of information that every graph has, so unless you tell us something more about what these degrees are, you can't use it to differentiate your graphs from arbitrary graphs. Same for "the number of paths".
David Eppstein
CC BY-SA 3.0
2017-03-11T11:13:43.213Z
You're right, I just wanted to make clear that not given information about the neighbors of the nodes. And that information is different than the general graph in a given situation. In addition I want  to understand is there anything smart we can say from those given (and by combination of them), when we  specifically  deal with a planar graph.
user1387682
<graph-theory><graph-algorithms><planar-graphs>
What can i learn about a graph about which only certain properties are known
user1387682
# What can i learn about a graph about which only certain properties are known

(Asked by: username_0 on 2017-03-06)

1) Suppose we are given the following facts about a graph. What can we conclude/compute beyond these facts?

* The fact that graph $G(V,E)$ is planar, and thus that it is 4-colorable,
* The degree of each vertex, and
* The number of paths of length $j$ in the graph for all $j \in \{1,...,n\}$.

Keep in mind that graph is not given (so in particular the neighbors of each vertex are not known).

2) What computations can be performed on a graph given in this manner that are more efficient than the corresponding computations on a general graph?

Thanks!

**Tags:** graph-theory, graph-algorithms, planar-graphs

> **Comments:**
> **username_1**: There is a lot of work on graphs with a given degree sequence, at least as far back as the Erdős-Gallai theorem.  Path sequences have been less studied, perhaps just limited to a 2015 paper by Bakalarski and Zygadło.  I'm not aware of any work that combines both degree and path sequences.  
> **username_2**: One of these things is not like the others. "The fact that the graph is planar" is something that constrains the graph, and might lead to algorithms more efficient than for arbitrary graphs. "The degree of each vertex" is a piece of information that every graph has, so unless you tell us something more about what these degrees are, you can't use it to differentiate your graphs from arbitrary graphs. Same for "the number of paths".  
> **username_0**: You're right, I just wanted to make clear that not given information about the neighbors of the nodes. And that information is different than the general graph in a given situation. In addition I want  to understand is there anything smart we can say from those given (and by combination of them), when we  specifically  deal with a planar graph.  

---

## 0 answers

