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

53 views

### Infinite resistor problem from a graph theory standpoint

I am trying to understand the infinite grid of resistors problem from a graph theory stand point(classic xkcd/google problem). Since effective resistance is the same as the commute time, this is ...
29 views

32 views

### Graph's Matching and edge covering

Let $G$ be a graph and $M$ a match with maximum size and $F$ an edge cover with minimal size. Prove that: $|M|+|F| = |V|$ That means that the number of all Matches with maximum size and the number of ...
36 views

### How many distinct directed acyclic graphs are there?

Given $|V|=4$ and $|E|=3$, how many distinct directed acyclic graphs can be formed? Isomorphic graphs should be counted as one. There is one where three periphery nodes point to a central node. ...
50 views

### proof of Triangle Removal Lemma

Where can I find a proof of the following version of Triangle Removal Lemma (or any version equal to it)? Let $G(V,E)$ be a graph on $n$ vertices such that it contains $\varepsilon n^3$ triangles, ...
85 views

### Integral identity graphs — smallest example

From Paulus Graphs. "The (25,2)-, (25,4)-, and (26,10)-Paulus graphs have the apparently rather unusual property of being both integral graphs (or asymmetric) and identity graphs (a graph spectrum ...
54 views

### Find the Eigenvalues of Petersen Graph

Petersen graph is k-regular graph on $n$ vertices and $m$ edges. We can find eigenvalue of $k-regular$ graph by characteristic polynomials of $G$ (denote $\chi_G (x)$) and $L(G)$ (denote $\chi_L (x)$)...
19 views

### Adjacency matrix is totally unimodular

Prove that the adjacence matrix of a simple graph is totally unimodular... I know incidence matrices are totally unimodular because in every column there is a 1 and a -1... makes things easier. Any ...
147 views

### A graph problem

Consider the following graph problem. We are given a set of vertices $A_i$, $B_i$, and $C_i$ where $i \in \{1,2,3 \}$. For each vertex, there is a corresponding weight where the weight of vertex $A_i$ ...
27 views

### Finding a recurrence for number of paths in a certain tree

I have a graph which looks like this: The question is to find a recurrence for $a_n$ - the number of paths of length $n$ that start in vertex $A$. How do you tackle these kind of problems? There is ...
30 views

27 views

### Calculate order of a graph from size of graph and size if its complementary.

Given the order of a graph (without loops) n, which size is 56. And its complementary graph which size is 80. How to find out the value of n?
37 views

### Uniqueness of graph neighbourhood sizes

I was thinking about graphs the other day, and had the following questions which I suppose fall under the topic of graph reconstruction. I am not very familiar with the literature, so in case this ...
11 views

### Corona of two graphs and Cartesian product of two graphs

I would like to know whether corona of two graphs is defined for two graphs with disjoint vertex set?? Also I would like to know whether Products of of two graphs (Cartesian, tensor,strong, ...
23 views

### Implicitization Problem on Graphs?

I learnt the implicitization problem for varieties in introduction course on Algebraic Geometry. I am trying to understand how to formulate a similar implicitization problem on graphs where the ...
23 views

### Arc-bases and Point-bases: when are they different for finite digraphs?

Definitions Given a digraph $D=(X,U)$, a point-basis of a digraph $D$ is a minimal vertex set from which a dipath exist to every vertex in $D$. An arc-basis is a minimal arc-reaching set. A subset ...
42 views

### Characterization of bicycle graphs

By "bicycle graph" I mean a minimal connected simple graph with at least two cycles. From Wikipedia: There are three possible types of bicycle: a theta graph has two vertices that are connected ...
54 views

### Non-trivial graph automorphism groups with $D_n$ as subgroup

I understand that the automorphism group of an $n$ cycle graph is the dihedral group $D_n$ of order $2 n$. From the comment of @Christian, I also understand that $S_n$ is the automorphism group of the ...
87 views
+50

### 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

35 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 ...
60 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 ...
80 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 ...
56 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 ...
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 (...