# Questions tagged [graph-theory]

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.

4,581 questions
2k views

### Mondrian Art Problem Upper Bound for defect

Divide a square of side $n$ into any number of non-congruent rectangles. If all the sides are integers, what is the smallest possible difference in area between the largest and smallest rectangles? ...
968 views

478 views

### Genus of the graph $K_{4,2,2,2}$.

What is the genus of the complete $4-$partite graph $K_{4,2,2,2}$? What i know: Since $K_{4,4,2}$ is a subgraph of $K_{4,2,2,2}$, and genus of $K_{4,4,2}$ is 2, $K_{4,2,2,2}$ has genus greater than ...
251 views

### Reconstruction Conjecture and Partial 2-trees

Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old. Searching relevant literature,...
475 views

### What is the Probability of Transmission Between Two Nodes in a Neural Network?

I have a network which is an Erdős–Rényi graph. It is a simple neural network with degree 0.7N where N is the number of nodes. Each weight between neurons is 1/N, meaning that if node n has fired ...
509 views

### Probability of the existence of a path of a specified length between any tw0 vertices in a random graph

Let $G$ be a graph with $n$ vertices, whose average degree is $k$. What is the probability that between any two vertices, there exists a path of length at most $l$? NOTE: For the above problem the ...
366 views

### Every 4-regular simple graph contains a 3-regular subgraph

The following result was conjectured by Berge & Sauer, and proved by Tashkinov [T]. Theorem A. Every 4-regular simple graph contains a 3-regular subgraph. A simple graph is the one with no ...
188 views

### Frogs jumping on trees

The frog game on a Tree: Default start of the game is placing one frog on each node (vertex). The goal is to move all the frogs to one single node. A single move consists of moving all $n$ frogs from ...
103 views

### Algorithms for “pleasing” drawings of planar graphs, possibly on sphere

What algorithms exist to draw planar graphs without edge crossings in a way that they are easy to interpret by humans? There are multiple algorithms that can handle any planar graph, such as Schnyder'...
260 views

### Quotient Groups and Covering Spaces in Painting Hanging

Consider the $1$-out-of-$n$ painting hanging problem: Given $n$ nails in a wall, how can we hang a painting such that upon removal of any nail, it falls. This has a nice interpretation as a problem in ...
313 views

### Number of sets of vertices whose union of neighbours contains exactly $k$ vertices

Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows: For example, $g$ for $n=3$: If I ...
799 views

### How many edges does an Erdős-Rényi graph have to have, to almost surely have a component with multiple cycles?

An Erdős-Rényi graph is a random graph, selected according to the distribution obtained one where we have some number $n$ of nodes, and some probability $p$ of each potential edge being present....
267 views

### Branching processes and couplings

A text I am reading is discussing ways to couple branching processes, and describes the following 2 pairings, the latter of which I am failing to understand. (I include the former for the sake of ...
382 views

### Edge Coloring of Kneser Graphs

Kneser graphs $KG(n, k)$ are well known: the vertices are all $k$-subsets of $\{1,2,\dotsc,n\}$ with two sets connected iff they are disjoint. If the graph is odd (i.e., has an odd number of vertices) ...
213 views

### Graceful graphs with Valence $k$

For a graceful graph ( code ), vertices are labeled with values from 0 to $e$ so that the $e$ edge differences are all values from 1 to $e$. $K_3$ is the minimal valence 2 graph with $e=3$. $K_4$ is ...
98 views

175 views

### Counting finite series with a given property

Given a natural number $n$, I'm trying to count the number $f(n)$ of series $a_1+a_2\dots +a_k,$ unique up to reversal (so $a_1+\dots a_i \dots +a_k$ and $a_k+ \dots a_{k-i+1}+\dots a_1$ are ...
152 views

### Heuristics for topological sort

I have a number of modules connected in a Directed Acyclic Graph. My problem is to find an optimal execution order (minimize the total execution time). Any topological sort suffices for a valid ...
569 views

### How is graph theory used to solve problems in number theory?

What are some applications of graph theory in number theory? How can a graph theory approach be useful to solving number theory problems? In general, is graph theory ever useful in making number ...
145 views

412 views

### Oblongs into minimal squares

Consider $a(n)$, the minimal number of squares into which the oblong of size $(n+1)\times(n)$ can be divided. What is the behavior of $a(n)$? The first 379 terms of the oblong square packing sequence ...
699 views

### Using Group Theory to Solve this IMO problem

A few weeks ago, I found a fascinating solution to a USAMO combinatorics problem that used group theory. Look at the 2nd solution on this link to view it. I think there might be a way to use group ...
240 views

### A game may related to graph theory or topology

Last Sunday, I played a game with a group of people. The game is as follows: A group of people form a circle as shown below: Each person must remember how he/she is linked with his two neighbours. ...
455 views

### Problem with an algorithm to $3$-colour the edges of cubic graphs

I'm currently trying to implement an algorithm to $3$-colour the edges of cubic graphs. (I want to do this with Matlab's Symbolic toolbox). After restricting to planar graphs to ensure the existence ...
724 views

### What can we say about two graphs if they have similar adjacency matrices?

Suppose we have two (finite, simple, undirected) graphs, what can we say about these graphs if they have similar adjacency matrices? Observations to begin with: If $G_1$ and $G_2$ are isomorphic, ...
294 views

### Enumerate graphs with hexagonal faces

How many are there non isotopic (in a sphere) embeddings of graphs with $n$ vertices, such that all faces are hexagons (including external face)? A given graph and its mirror image can be counted as ...
91 views

### The number of Hamiltonian paths in a tournament is always odd?

A tournament is defined as an orientation of a complete graph. Prove or disprove the following statement: In a tournament, there are exactly an odd number of Hamiltonian paths. In all cases I’ve ...
187 views

### Polynomials for Bicubic Planar Dessin d'Enfants

A dessin d'enfant is a graph, with its vertices colored alternately black and white, embedded in ... a plane. For the coloring to exist, the graph must be bipartite. ... The ... embedding may be ...
180 views

### Dividing a graph into $k$ subgraphs

Is there an algorithm for finding the number of ways a given connected graph can be divided into $k$ connected subgraphs? I've searched the Web for an answer, but perhaps I'm using the wrong words as ...
285 views

### Generalisation for k independent paths

I was studying graph theory and came across this problem: Show that a graph with $n > 3$ vertices and $m > \frac{3(n - 1)}{2}$ edges contains two vertices joined by three independent paths. ...
LG android cell phones have locking screens with $9$ points to be traced in any pre-specified fashion (drawing pattern) so as to join $\geq 4$ points without including any points more than once. ...
A Latin square graph of a Latin square $L=(L_{ij})$ of order $n$ has $n^2$ vertices $(i,j)$ and edges between distinct vertices $(i,j)$ and $(i',j')$ whenever (a) $i=i'$, (b) $j=j'$, or (c) \$L_{ij}=L_{...