# Tagged Questions

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

126 views

### Maximal unit lengths in 3D with $n$ points.

Given $n$ points in 3D space (V), what is the maximal number of unit distance lengths (E) between those points? Here are a few possibilities. Some of them are chromatic spindles. ...
30 views

37 views

### What is the necessary and suffices condition to build an r -regular graph?

I need to show what is necessary and suffices to have an r-regular graph with n vertices. where $n > r+1$ One way is to build that r-regular graph with n vertices ...
61 views

### Is every finite category identifiable with a directed multigraph? (and vice versa?) [duplicate]

What seems implicit in this talk on youtube, is the claim that every directed multigraph (with loops) can be identified with a finite category and vice versa, if we consider the paths of the directed ...
82 views

### Is “Connected Component” unique for each graph?

Definition A connected component of an undirected graph $G$ is a subgraph where any two vertices are connected by paths. A connected component is a maximal connected subgraph in $G$. Consider a ...
64 views

### Show that for each of the following graphs G there exists up to isomorphism precisely one category A with G(A) = G.

I was working through the exercises in Abstract and Concrete Categories: The Joy of Cats (http://katmat.math.uni-bremen.de/acc/acc.pdf) and I was stuck on exercise 3A.(d). It seems to me that the ...
98 views

### Eigenvalues of periodic lattice Laplacian?

Consider the graph given by taking a rectangular lattice with $m$ rows and $n$ columns and joining each vertex to its four nearest neighbors, where vertices on the boundary are connected periodically (...
33 views

30 views

### Prove a cube graph has no even walks?

The following question was in my exam, and I didn't even have any idea on how to start, so I'm quite curious to see a proof. I was given a cube graph (the one on the left): The question was as ...
17 views

### finding proper coefficient for the two graphs to intersect at one point only

We have two functions such as $y=\ln(x)$ and $y=cx^{1/2}$ and I look for the proper positive coefficient $c$ which satisfies that the graphs of the functions above intersects at only one point. If we ...
155 views

### Is there a monoid structure on the set of paths of a graph?

Given a graph G, and the set of paths in G called PathG. Is there a monoid structure on PathG? Will concatenation be the multiplication formula? even if it's not defined for some paths? What about ...
57 views

### $A^A$ in category of graphs

(reference is Lawvere/Schanuel, Session 31, Ex. 1) I'm trying to calculate the exponential object $A^A$ and its evalution map $e \colon A \times A^A \to A$ in the category of graphs, where $A$ is the ...
28 views

### Given a weighted graph, how to find a node sequence that closed nodes have strong connection.

This may be a graph theory question: Given a weighted undirected graph, large weight means the correlation of the two nodes is big. How can I generate a node sequence such that nodes nearby have ...
65 views

### How many sets correspond to connected graphs

I'm trying to solve this project euler problem. I don't want to get too much help, since that would defeat the purpose, but I'm hitting a wall, so I'm asking a related problem here, from which I'll ...
28 views

### Planarity found in inducing $K_5$ [duplicate]

I was interested in studying whether or not if when we remove an arbitrary two edges from $K_5$, we get a planar graph. I understand that a planar graph has at most $3v-6$ edges, where $v$ is the ...
74 views

### Is there a proof that any graph is “drawable” on a 2D surface? [closed]

Are there any theorems that say something formal about the fact that any graph is drawable on a 2D surface, and can be mapped to a 2D array of pixels if the pixels are infinitely small? EDIT: No ...
52 views

### What are some applications of vertex separators?

What are applications of finding a vertex separator that minimizes a cut in a graph. To clarify the problem I am talking about is is given a graph of n vertices and a partition $m_1,m_2,..,m_k$of ...
20 views

### Maximum (edge)weight connected subgraph of an undirected graph.

Let G be a undirected graph with weighted edges. I want to find a connected subgraph which has at most L nodes(vertices) whose sum of edges is maximum. It sounds similar to MWCS or PCST but here only ...
37 views

### Find a DFS,BFS spanning tree.

Is my answer right? I think I understood the definition of BFS and DFS spanning tree, but I'm not sure my answer is right. If it is wrong, please correct it.
18 views

### Creating Barabási–Albert(BA) graph with spacific node and edgs

I am trying to construct a BA graph with 500 nodes and about 37000 edges. The number of edges to attach from a new node to existing nodes should be at least 91 to make enough number of edges. I ...
32 views

### Which vertex-transitive planar graphs represent non-self-intersecting polyhedra?

Consider an infinite planar graph with the following properties. Its vertices all have valence $3$. The faces all have $5$ edges. Now put it in cartesian space and require that the faces are all ...
27 views

### Topological sort into a limited number of bins, each with limited capacity

I'm working on a scheduling/design tool for educational courses. I have lists of courses, some which require others to be taken first (dependencies), others that require courses to be taken together ...
44 views

### Permutation of keys inserted into a tree?

Give the fraction of permutations of the keys $A$ through $G$ that will, when inserted into an initially empty tree, produce the same Binary search tree as does $A$ $E$ $F$ $G$ $B$ $D$ $C$ ANSWER: (...
17 views

### How can I count the number of faces in $K_2$?

I studied that in $K_2$ we have $V=2$, $E=1$, and $F=1$, and in $K_3$, we have $V=3$, $E=3$, and $F=2.$ But where is the face in $K_2$? There is only one line in there.
44 views

### Prove that a sequence of degrees can be the degrees of a simple graph

Hi there I need to show that the sequence $s(n) = \{1,1,2,2,3,3,4,4,...,n,n\}$ can be the degrees of the vertices of a simple graph, $\forall n\geq 1$. So far I have tryied to prove this by induction ...