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.

46
votes
0answers
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? ...
21
votes
0answers
968 views

Blocking directed paths on a DAG with a linear number of vertex defects.

Let $G=(V,E)$ be a directed acyclic graph. Define the set of all directed paths in $G$ by $\Gamma$. Given a subset $W\subseteq V$, let $\Gamma_W\subseteq \Gamma$ be the set of all paths $\gamma\in\...
21
votes
0answers
230 views

Does $K_{70,70}$ decompose into subgraphs isomorphic to $K_{1,1}$ through $K_{24,24}$?

The complete bipartite graph $K_{n,n}$ has $n^2$ edges. There's a curious number quirk that $$70^2=4900=1^2+2^2+\cdots+24^2.$$ This motivates the question: Question: Does $K_{70,70}$ decompose into ...
19
votes
0answers
671 views

Analyzing a class of vertex-deletion games

As part of the discussion on this question (Permutation Game Redux), a simple vertex-deletion game was proposed. The game is very simple. Disconnect. Players alternately remove vertices from a ...
16
votes
0answers
1k views

Minimal time gossip problem

The gossip problem (telephone problem) is an information dissemination problem where each of $n$ nodes of a communication network has a unique piece of information that must be transmitted to all the ...
14
votes
0answers
166 views

graph with many authomorphisms

Let $G(V,E)$ be an undirected graph, potentially with loops and multi-edges. Assume the following two properties hold: $\forall a \in V(G), \exists f \in aut(G), f(a) \ne a$ $\forall f\in aut(G), \...
14
votes
0answers
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 ...
14
votes
0answers
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,...
12
votes
0answers
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 ...
12
votes
0answers
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 ...
11
votes
0answers
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 ...
10
votes
0answers
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 ...
10
votes
0answers
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'...
10
votes
0answers
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 ...
10
votes
0answers
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 ...
10
votes
0answers
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....
10
votes
0answers
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 ...
10
votes
0answers
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) ...
9
votes
0answers
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 ...
9
votes
0answers
98 views

Flimsy bound of maximal independent set

Problem: For graph $F$, let $\alpha(F)$ denote the maximal size of $F$'s independent vertices set. $G$ is a connected simple graph such that $\alpha(G)=a$, and for any edge $e$ of $G$, $\alpha(G-e)...
9
votes
0answers
244 views

When a matrix has same eigenvalues of its column-swapped version?

What are the properties needed for a matrix $A$ to have $\mbox{Spec}(A)= \mbox{Spec}(A \cdot P)$, where \begin{equation} P = \begin{pmatrix} 0 & \cdots & 0 & 1 \\ \vdots & \...
9
votes
0answers
509 views

Theoretical link between the graph diffusion/heat kernel and spectral clustering

The graph diffusion kernel of a graph is the exponential of its Laplacian $\exp(-\beta L)$ (or a similar expression depending on how you define the kernel). If you have labels on some vertices, you ...
9
votes
0answers
177 views

Given $100$ coplanar points, no $3$ collinear, then at most $70$ percent triangles formed using these points are acute-angled

(IMO-$1970$) Given $100$ coplanar points, no $3$ collinear, prove that at most $70$ percent of the triangles formed using these points are acute-angled. I know that one solution proceeds by showing ...
9
votes
0answers
115 views

How many hamilton paths can a non-hamiltonian graph have?

What is the maximum number of hamilton paths a graph with $n$ vertices can have without having a hamiton cycle ? If my turbo pascal program works well, the first few values for $3,4,...$ vertices ...
9
votes
0answers
2k views

Random graph connectivity, and the existence of isolated vertices

Here $G_{n,p}$ represents the Erdős-Rényi random graph model, where the graph has order $n$ and each edge is added independently with probability $p$. I am faced with proving the following claim: ...
9
votes
0answers
233 views

What do we know about general graph degree sequences?

The sequence of sizes of single vertex cuts of a graph is called its degree sequence. Is there an agreed-upon name for the sequence of sizes of $k$-vertex cuts? What can be said about two graphs which ...
8
votes
0answers
93 views

Coloring the Natural Numbers

This problem appears on page $134$ of Peter Winkler's Mathematical Mind-Benders. Can you color the natural numbers $\{0,1,2,\dots\}$ with finitely many colors, in such a way that the sum $x+y$ ...
8
votes
0answers
266 views

Interesting sequence involving prime numbers jumping on the number line.

Udpate 4: Trying to characterize finite and infinite cycles. Update 3: All primes $a_0\ge29$ seem to either have infinite cycles or finite non-terminating cycles that converge to infinite cycles of ...
8
votes
0answers
218 views

Counting the labellings of paths in perfect binary trees

Suppose that we have a set of $n$ labels $L = \{\ell_1, \ell_2, \ldots, \ell_n\}$ and a perfect rooted binary tree $T$ of height $r \leq n$. For my purpose, the tree containing a single node will be ...
8
votes
0answers
69 views

What can we say about the equivalence relation defined such that $G \sim H \Longleftrightarrow Aut(G) \simeq Aut(H)$?

Given two finite graphs $G, H$, I say that $G \sim H$ if and only if $Aut(G) \simeq Aut(H)$. We define $[G] = \{H \mid Aut(G) \simeq Aut(H) \}$ for any graph $G$. Due to theorems by Erdos and others ...
8
votes
0answers
272 views

How does the topology of the graphs' Riemann surface relate to its knot representation?

Let me give a worked-out example: The following cubic planar non-simple graph $\hskip2.3in$ has the adjacency matrix $A=\pmatrix{0&3\\3&0}$. The graph has three faces, so the rank of $G$ is $...
8
votes
0answers
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 ...
8
votes
0answers
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 ...
8
votes
0answers
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 ...
8
votes
0answers
145 views

A connection between nonplanar complete graphs and the alternating group?

I went to an undergrad's senior honors thesis presentation a few days ago. She was discussing crossing numbers and mentioned that complete graphs $K_n$ are nonplanar iff $n \geq 5$. ?Coincidentally? $...
7
votes
0answers
66 views

Partitioning a graph in cycles of four

I have the following question: Suppose that in a simple undirected graph with $4n$ vertices, each vertex has degree at least $2n$. Is it true that we can always partition the set of vertices ...
7
votes
0answers
252 views

How to prove if an N size jigsaw puzzle is solvable.

Let's say we have a jigsaw puzzle with N pieces. Each piece has 4 sides and can only have one of three fits: a straight fit, a concave fit and convex fit. A side can only fit with another side if both ...
7
votes
0answers
87 views

Mean square density loss when removing the exceptional set of a graph equipartition

An equipartition of a graph $G$ is a partition $V_1,...,V_k$ of its vertices to sets that are as equal as possible: $||V_i|-|V_j||\leq 1$. We define the energy of the partition to be $q(\mathcal P)=\...
7
votes
0answers
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 ...
7
votes
0answers
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 ...
7
votes
0answers
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. ...
7
votes
0answers
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 ...
7
votes
0answers
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, ...
6
votes
0answers
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 ...
6
votes
0answers
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 ...
6
votes
0answers
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 ...
6
votes
0answers
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 ...
6
votes
0answers
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. ...
6
votes
0answers
83 views

Number of phone locking patterns

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. ...
6
votes
0answers
69 views

Do the two order-4 Latin square graphs have the same number of Hamilton cycles?

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_{...