Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

15
votes
2answers
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 ...
3
votes
2answers
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 ...
1
vote
0answers
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$...
2
votes
1answer
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 ...
1
vote
0answers
103 views

Characterization of k-walk-equivalent graphs

Let $G=(V,E)$ be an undirected graph. A walk of length $k$ in $G$ is a sequence of vertices $v_1,v_2,\ldots,v_{k+1}$ in $V$ such that $(v_i,v_{i+1})\in E$ for each $i=1,2,\ldots,k$. Call two graphs $...
2
votes
0answers
38 views

On the frequency with which a vertex can be added to the independent sets in a graph

Let $i(G)$ denote the number of independent sets of vertices of a graph $G$, write $G-v$ for the graph $G$ with the vertex $v$ removed, $G-H$ for the graph $G$ with the subgraph $H$ removed, and $N_k(...
2
votes
1answer
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 ...
6
votes
1answer
272 views

A permutation problem

Here I ask a question on permutations of $n$ distinct real numbers. QUESTION: Let $a_1,a_2,\ldots,a_n\ (n>1)$ be (pairwise) distinct real numbers. Is there a permutation $b_1,\ldots,b_n$ of $a_1,\...
1
vote
0answers
49 views

An “almost separable” optimization problem on a graph

I am trying to solve an unconstrained optimization problem with the following properties: I am given a graph $G=(V,E)$ with functions $f_{ij}:\mathbb{R}^2\to \mathbb{R}$ for each edge $(i,j)$. I am ...
1
vote
0answers
37 views

Family of rooted trees parameterized by binary sequences

Let $A=\{1,2\}$. For any $d \in A$ and any sequence $a=(a_1,a_2,\dots)\in A^{\mathbb N}$ the associated rooted tree $T(d,a)$ is recursively defined in the following way. The degree of the root of $T(d,...
2
votes
1answer
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)$ ...
3
votes
2answers
178 views

Computer program for counting graph homomorphisms

I would like to ask is there a computer program for counting graph homomorphisms?
0
votes
0answers
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 ...
1
vote
0answers
65 views

Bipartite clustering is NP-hard?

Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, ...
16
votes
0answers
249 views

Straight-line drawing of regular polyhedra

Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane). For example, ...
2
votes
1answer
73 views

Minimal cutting sets in connected graphs

Let $G=(V,E)$ be a simple, undirected and connected graph. We say that $S\subseteq V$ is a cutting set if $S\neq V$ and the induced subgraph on $V\setminus S$ is not connected any more. If $S \...
0
votes
2answers
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$, ...
4
votes
1answer
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 ...
7
votes
0answers
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 ...
4
votes
1answer
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. ...
9
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
11
votes
3answers
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 ...
1
vote
1answer
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?
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
8
votes
1answer
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 ...
2
votes
0answers
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)$, ...
4
votes
0answers
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 ...
-1
votes
2answers
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 ...
1
vote
0answers
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 ...
2
votes
0answers
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$ ...
6
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
2answers
143 views

Injective, but no bijective neighborhood map

The concept of neighborhood maps was looked at in a previous question. Let $G= (V,E)$ be a simple, undirected graph. For $v\in V$ we set $N(v) = \{w\in V: \{v,w\} \in E\}$. Note that we always have $...
0
votes
0answers
21 views

Complexity of Minimum Spanning Trees with Lower Degree Bounds

It is known, that the problem of calculating Minimum Spanning Trees with an upper bound on the vertex degrees is NP complete. Question: what is the complexity of calculating Minimum ...
1
vote
1answer
50 views

Existence of dense graph with relatively small codegree?

Let $n$ be some parameter tending to infinity. I am wondering does there exists some kind of graphs $G$ on vertex-set $[n]$ with maximum degree less than $D$, so that $D\ge n/w_1(n)$, $e_G$, the ...
7
votes
2answers
221 views

complicated combinatorial algorithms with good descriptions

For educational purposes, I am looking for an example of a complicated, elementary, but very well-explained combinatorial algorithm. Such an example might be a bijection between two easily described ...
0
votes
1answer
96 views

Description of Linear Time Algorithm for TSP in Halin Graphs

I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in "G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling ...
0
votes
1answer
46 views

Degree Distribution of Planar Minimum Spanning Trees

Question: how are the vertex degrees of MSTs of the corresponding points that are uniformly and independently distributed in a square region of the euclidean plane and the edges being weighted ...
0
votes
1answer
76 views

Maximum partition of bipartite graph

Let $G = (U, V, E)$ be a bipartite graph. Let $w: E \to \mathbb{R}$ be a weight function on the edge set $E$. Given subsets $U_1,\ldots, U_k \subset U, U_i\cap U_j = \emptyset$ and a partition $V_1,\...
1
vote
2answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
63 views

Growth models with lookahead

Given a connected graph $G$ with a connected subgraph $H$, we can consider the uniform distribution on the set of all sequences $H_0, H_1, \dots, H_r$ where $r = |E(G) \setminus E(H)|$, $H_0 = H$, $...
7
votes
1answer
147 views

A Question on Graph Limits

I have a somewhat technical question about the concept of graph limits: Suppose that $G_n$ is a sequence of labelled, simple, unweighted graphs, and let $W_n$ denote the graphon of $G_n$ (i.e. $W_n(x,...
3
votes
0answers
108 views

Constructing Graph V from De Grey´s Minimum Bound For the Chromatic Number of a Plane

Background information: In section 4.2, paragraph 2 of De Grey´s recently published paper (De Grey's Paper pdf), he constructs a graph V, which is used to construct the graphs W, M, and eventually ...