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

17 views

### Canonical forms for matrices with binary elements.

Based on this answer to a combinatorics question I grew curious of results regarding similarities or canonical forms of matrices fulfilling these criteria: Elements of matrix are binary valued ...
11 views

### Wouldn't the asymptotes of the 2D projection of the inverse of the Riemann Zeta function show the real part of all the non-trivial zeros?

Can somebody provide a visualization of $z=\frac{1}{\zeta(x+iy)}\pm N$ for some large $N$ projected onto the $xz$-plane? I would imagine that if we found any asymptotes converging anywhere other than ...
29 views

### Find subgraph with maximum number of edges

Suppose there is a simple graph G. Is there a way to find a subgraph with a maximum of edges, for a certain number of vertices m?
36 views

### Probability Assessment of Interactive Markov Chain (IMC)

Firstly, consider a Markov chain in your mind. Probability of each state of the Markov chain can be obtained by following Chapman–Kolmogorov equation. $$P(n\Delta t) = M^{n}P(0)$$ where P is the ...
121 views

### $(r+1)$ Clique of Induced subgraph and Turan’s theorem

$G$ is a $s$ regular graph. $A$ is a set of vertices where $|A| = s$ and $A \subseteq G$. $E$ is the number of edges of $G$. $n$ is the total number of vertices of $G$. Problem: Find the lower ...
42 views

### Graphs with disjoint edge sets

Consider a fixed set of vertices $\{v_1,v_2,\ldots,v_m\}$ and a family of graphs $G_1, G_2, \ldots, G_n$ on these vertices such that no two graphs share an edge. In other words, if $E(G_i)$ is the ...
21 views

### Yet another curious convolution

Some time ago, I found the following algorithmic problema: Count the number of distinct unrooted, unordered, labeled trees of $n$ nodes where each node has at most $k$ neighbors. Given that the ...
36 views

### Expected number of random sub-cliques neccessary to cover a complete graph

I have the following problem: Given a complete, simple graph, i.e., a graph $(V,E)$ where every possible edge is realized, so $|E| = \frac{|V||V-1|}2$. Now consider complete sub-graphs, or ...
40 views

### Is there a name for this particular kind of tree graph?

I've recently encountered a problem which heavily involves analysis of structures analogous to weighted trees with no nodes of degree two (such a node along with its adjacent edges would be ...
86 views

### The Earth-Moon Map Problem

The following is the Sulanke Earth-Moon Map. A planet and moon have each been divided into eleven contiguous regions. In both maps, the regions 1-3, 3-5, 5-2, 2-4, and 4-1 do not touch, while all ...
30 views

### Binary Minimum Spanning Tree (from complete graph)

Given a weighted complete graph (or more exactly, a matrix of pairwise metric distances between vertices), I need to find a good approximation of the binary spanning tree of lowest total cost. There ...
32 views

### On the LowerBound for the number of edges of a simple connected graph on $n$ vertices.

We know that if $G$ is a simple graph on $n$ vertices and if $G$ has $k$ components then the number of edges $m$ of $G$ has the lower bound: $n-k\leq m$. The proof of one of a reference book on ...
31 views

### What kind of topological sorting exists in graph theory and what are their graphic plotting?

I know that there is at least two kinds of topological sorting: "by rank" and by"level" a level of a vertex is the maximal length of a path with x as an extremity. a rank of a vertex is the maximal ...
21 views

### Name of operation: changing the root of a rooted tree

What is (if any) the name of the operation of changing the root of a rooted tree? Picking a vertex which is not the root, then reorienting the edges in such a way that the vertex becomes the root?
37 views

25 views

### Obtain cycles with $a <$ nr. of edges $< b$

I have a chemistry/mathematical problem and I would like to get your opinion. Imagine you are generating a planar, cyclic molecule, with a total $N$ is the number of atoms. By Euler graph theory, the ...
48 views

### To find out the minimum required jumper number between objects

I try to find out the minimum required jumper number for connection between objects. The rule is : all objects are on a plane and need to connect all objects with only one connection. The minimum ...
47 views

### Independence of Events in Lovasz Local Lemma

Let $G$ be a (finite) graph with maximum degree $d$ and vertices $v_{1}, \dotsc ,v_{n}$. Let us associate an event $A_i$ with $v_i (i = 1, . . . , n)$ and suppose that $A_i$ is independent of the ...
How many different triangles are there in $K_5$? The Answer is 35.(The Moscow Mathematics Puzzle) Then I asked what about $K_6$, $K_7$ and so on ...? With my intuition I arrived at this ...