# Questions tagged [graph-theory]

Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.

3,400 questions
206 views

### Labeling binary trees so that adjacent vertices differ by a power of two

Let $T$ be a finite rooted binary tree (where "binary tree" means that each node has at most two children, possibly less) with $n$ nodes in total. Is there a labeling of the nodes of $T$ with the ...
234 views

### Orientability of $\mathbb{Z}^n$

For any set $X$ set $[X]^2 = \{\{x,y\}: x,y\in X, x\neq y\}$. If $n\geq 2$ is an integer, we endow $\mathbb{Z}$ with a graph structure in the following way. If $x,y\in \mathbb{Z}^n$ we say $x,y$ are ...
39 views

### $\exp(-Cn^{\epsilon})$ estimate for probability of Brouwer-Haemers condition in Erdos-Renyi-like random graph

For any $n$-vertex graph $G$, we have the inequality $\lambda_i^{L_G}\geq D_i-i+2,$ where $L_G$ denotes the Laplacian of $G$ and $\lambda_i^{L_G}$ denotes the $i^\text{th}$ largest eigenvalue and $D_i$...
131 views

### When does a row standardized adjacency matrix have a real spectrum?

A colleague in spatial statistics was looking at a map with about 600 regions. For the application she's considering, the induced adjacency matrix had some undesirable properties (where two regions ...
103 views

97 views

### $\omega$-Hamilton paths in $\mathbb{Z}^n$

For any set $X$ set $[X]^2 = \{\{x,y\}: x,y\in X, x\neq y\}$. If $n\geq 2$ is an integer, we endow $\mathbb{Z}$ with a graph structure in the following way. If $x,y\in \mathbb{Z}^n$ we say $x,y$ are ...
272 views

75 views

### On the laplacian of connected, undirected, multigraphs without loops

Let $G$ be a connected, undirected multigraph, without loops. Let $L_G = D_G - A_G$, where $D_G= diag (val (v_1), \ldots , val (v_n) )$ where $n$ is the no. of vertices of $G$ and $val (v_i)$ ...
178 views

### Computer program for counting graph homomorphisms

I would like to ask is there a computer program for counting graph homomorphisms?
46 views

### Fixed paths in Menger's Theorem

In a $k$-connected graph, if you have two disjoint sets $A,B$ of $k$ vertices each, then by Menger's Theorem there exist $k$ vertex disjoint $A,B$-paths. However given an arbitrary $A,B$-path $P$, in ...
65 views

99 views

### Is there a standard name for this type of multidigraph?

A digraph (direct graph) consists of a set $V$ of vertices and a set $E$ of directed edges $v\to v'$. A multidigraph is a digraph in which $E$ is a multiset, so edges may appear multiple times in $E$, ...
91 views

### Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?

In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle ...
190 views

### A question related to Conways 99 graph problem

I have observed that the number of triangles $\frac{vk}{6}$ of a strongly regular graph with parameters $(v,k,1,2)$ is given by the coefficient $2(k-1)$ in the molien series of the "4-D extraspecial ...
142 views

### Citations graphs what is known?

There have been much research related to webgraphs and social graphs. They can be thought of a kind of random graphs, but the point is that they are different from the well-known Erdős–Rényi model. ...
287 views

### Are bipartite Moore graphs Hamiltonian?

This is motivated by a computer-generated conjecture that bipartite distance-regular graphs are hamiltonian. I decided to check the case of Moore graphs first. The cycles and complete bipartite ...
87 views

### Is this Graph Iteration Already Known?

When attempting to set up an ILP formulation for a weight-minimal cubic spanning tree (i.e. one with vertex degrees either 1 or 3) I needed connectivity constraint, but misremembered the contents of ...
106 views

### Juggling the Jacobi identity

View the Jacobi identity as a purely graphic thing (the IHX relation on trivalent graphs, possibly with open ends, edge-coloring is also allowed). By repeatedly applying it to a graph, can you derive ...
117 views

### Large complete minors of $\mathbb{Z}^\omega$

Let $x,y\in \mathbb{Z}^\omega$ and let $x,y\in\mathbb{Z}^\omega$ form an edge if there is $i\in\omega$ such that $|x_i - y_i|=1$ and $x_k = y_k$ for all $k\in \omega\setminus\{i\}$. $K_\omega$, the ...
926 views

### Cops, Robbers and Cardinals: The Infinite Manhunt

Cops & Robbers is a certain pursuit-evasion game between two players, Alice and Bob. Alice is in charge of the Justice Bureau, which controls one or more law enforcement officers, the cops. Bob ...
74 views

### Non hamiltonian k-regular bipartite graphs

For any $k \ge 3$ construct a non hamiltonian, connected k-regular bipartite graph. I have tried to find such graphs for small $k$-s but i got nothing. Can anybody help?
90 views

### Complete minors of the grid graphs $\mathbb{Z}^n$

Let $n>1$ be an integer. We say that two points $(x_1,\ldots,x_n),(y_1,\ldots,y_n)\in\mathbb{Z}^n$ are a member of the edge set $E_n$ if and only if $$\sum_{i=1}^n|x_i-y_i| = 1.$$ Question. Given ...
19 views

### Calculation of Vertex Weights for Combinatorial Optimization of Regular Spanners

Vertex Weights are a means to modify the weight of an edge by adding to it the weights of its adjacent vertices. The motivation for adding vertex weights to edge weights is two-fold: the relative ...
96 views

### Probability for a group of stones to live on an infinite Go board

Suppose on an infinite two dimensional Go board the tengen is occupied by a black stone, and every other grid point is occupied by a black stone, or a white stone, or nothing, with probability 1/3 ...
100 views

### Conditions for a matrix to be a Graph Laplacian [closed]

Let M be a symmetric non-negative definite $n\times n$ matrix. Let $K_n$ denote the complete graph on $n$ vertices. Under what conditions is it possible to assign edge weights to $K_n$ in such a way ...
383 views

### Graphs with only disjoint perfect matchings, with coloring

The following purely graph-theoretic question is motivated by quantum mechanics. Definitions: A bi-colored graph $G$ is an undirected graph where every edge is colored. An edge can either be ...
193 views

### What is known about “graph algebras”?

In lack for a better name I call a "graph algebra" a simple undirected graph $G=(V,E)$ and a binary mapping $+:E \rightarrow V$ such that: (1) For all edges $(a,b)$ we have: $a+b \in N(a) \cap N(b)$, ...
51 views

### Separating stars and large intersections of cycles

Let $\Gamma$ be a finite simplicial graph. For every $k \geq 0$, let $C_k(\Gamma)$ denote the graph whose vertices are the induced cycles of $\Gamma$ and whose edges link two cycles if their ...
69 views

### On a condition concerning the number of neighbors in bipartite graphs

For any undirected simple graph $G=(V,E)$ we define for $v\in V$ the set $N(v) = \{w\in V: \{v,w\}\in E\}$. Suppose $A, B$ are finite, disjoint sets, and $G = (A\cup B, E)$ is a bipartite graph with ...
103 views

### Is the partition of bipartite graphs NP-hard?

I wonder if the following problem is NP-hard. Is it? Given a bipartite graph $G = (U, V, E)$ with weights $w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and nonempty disjoint ...
42 views

### Size of the last non-empty $k$-core of a random graph

Given $n$ and $p$ for $G(n,p)$, how to find the distribution of the size of the non-empty $k$-core with largest $k$? In particular, what is the probability (for any $n$ and $p$) that only $c$ ...
93 views

### What is the smallest number of vertices in a graph whose every orientation contains a directed straight path of length 3

For a graph $\Gamma$ and a digraph $\vec H$ we write $\Gamma\Rightarrow \vec H$ if any orientation of $\Gamma$ contains an isometric and isomorphic copy of the digraph $\vec H$. Since each graph ...
69 views

### The minimum possible degree of a graph of $n$ vertices, in which all pairs of nodes have a distance no more than $d$

Here the degree of a graph is the maximum degree of all the vertices in the graph. For example, when $n=4,d=2$, a cycle with 4 vertices is a solution, and a graph with 1 degree is not connected. So ...
143 views

139 views

### Extremal density of a graph without a non-backtracking $2k$-cycle

The current best bound for the maximum possible density of an $n$-node graph with girth (shortest cycle length) $>2k$ is of the form $$ex(n \ \mid \ C_{\le 2k}) = O(n^{1 + 1/k}),$$ while the ...
110 views

### Number of hypercube unfoldings

While writing the code for this answer, I noticed that I not only could calculate the number of unfoldings of the $4$-cube, but also the number of the $n$-cube for more values of $n$. Basically, we ...