All Questions
Tagged with planar-graphs algebraic-graph-theory
12
questions
1
vote
0
answers
65
views
Why is the formula of edges$=$nodes$-$1 for modeling radiality very slow?
Suppose $G$ is a graph. $E(G)$ and $V(G)$ denote the sets of the edges and nodes (vertices) of $G$, respectively.
I need a spanning subgraph of $G$ (let’s call the subgraph $g$). The subgraph must be ...
2
votes
1
answer
121
views
Vertex minors of paths
(Vertex Minor) A graph H is a vertex minor of G if H can be obtained from G by a sequence of vertex deletions and local complementation
(Local complementation) A local complementation $\tau_v$ is a ...
- 326
0
votes
0
answers
44
views
Comparing networks using graph theory
I'm new to graph theory so forgive if I use unconventional terminology. Please ask if there's any confusion regarding the statements I make.
I have a bunch of undirected, unweighted, simple graphs ...
- 326
1
vote
0
answers
34
views
Expand acyclic graphs to acyclic graphs
I am learning about Kruskal Algorithm to find minimal spanning trees. To show that the spanning tree which is constructed with that Algorithm is minimal, I need to prove this statement:
Let $G=(V,E)$ ...
- 973
3
votes
1
answer
333
views
Requirements for embedding a graph in n-dimensional euclidean space
Given a graph $G = (V, E)$, I want to embed it into a $n$-dimensional space $\mathbb{R}^n$, while respecting the following conditions:
Let $x_i$ be the $n$-dimensional embedding of vertex $v_i$.
If $...
- 157
3
votes
1
answer
270
views
Graphs on Cylinders
I know that nonplanar graphs can be embedded without self-intersection into a $g$-holed torus, for sufficiently large $g$. In particular, I know that $K_5$ and $K_{3,3}$ can be embedded into the torus....
0
votes
1
answer
65
views
Generalization of complete bipartite graphs [closed]
The concept of complete bipartite graphs can be generalized to define the
complete multipartite graph $K_{r_1, r_2, ..., r_k}$. This graph consists of $k$ sets of
vertices $A_1, A_2, ..., A_k$, with $...
- 3
1
vote
1
answer
269
views
number of closed-loop graphs in square lattice
Suppose I have a $N\times N$ square lattice. I want to know how many different closed-loop diagrams are there. The closed-loop diagrams can have no loop, one loop, two loops, etc. If two loops share ...
- 185
1
vote
0
answers
70
views
Materials to read for Graph Theory.
I am interested in graph theory and currently finished learning the basic knowledge in graph theory. Before I continue on to study the following three branch of graph theory, namely Topological Graph ...
- 1,718
7
votes
2
answers
261
views
Going with/against the orientation alternates along the Hamilton cycle?
Below you see an example of a bicubic graph consisting of faces with degree $4$ and $6$, which makes up the set of graphs of my interest and is a subset of the so called Barnette graphs.
$\hskip1....
- 18.6k
1
vote
1
answer
101
views
Surjective homomorphism preserves planarity?
I was just wondering if for surjective homomorphism of G to H, where G is planar hold that H is planar as well.
This is clearly false for non-surjective ones, but for surjective?
How it is with ...
user320254
1
vote
1
answer
6k
views
what is the maximum number of faces with n vertex in planar graphs?
what is the maximum number of faces with n vertex in planar graphs?
v=number of vertices
f= number of faces
for example if v=3 -> max(f)=2
v=4 -> max(f)=4 (a triangle with a point in inner face of ...
- 137