# Tagged Questions

**8**

votes

**1**answer

176 views

### Expansion in strongly regular graphs

Have you seen the following statement proven anywhere?
Let $G$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$ with $\lambda,\mu>0$. Then there is no set $A$ of at least $n/4$ ...

**11**

votes

**1**answer

285 views

### Travelling salesman: can the furthest-neighbour algorithm beat the nearest-neighbour?

This is a problem that has bugged me for quite some time, and I have not been able to find any documentation about it online. It is well known that the NN algorithm can yield the worst possible route ...

**1**

vote

**1**answer

55 views

### Duality and Euler paths in graphs

I'm computer scientist and in one of my researches I'm facing this question:
if I have a planar graph that admits an Euler path (i.e. has 0 or 2 odd degree vertices, as Euler's theorem says), then his ...

**9**

votes

**3**answers

257 views

### Labeling edges of an icosahedron with sum constraints

The question is inspired by this previous MO question. There it was shown that it's possible to label the edges of a cube by the numbers $\{1,2,\ldots,6,8,9, \ldots, 13\}$ in such a way that:
Three ...

**1**

vote

**0**answers

23 views

### Performance guarantee of RLF [closed]

I cannot manage to find the performance guarantee of the Recursive Largest First (RLF) algorithm for approximating the chromatic number of a graph.
I know DSATUR has a $\mathcal{O}(n)$ guarantee, ...

**3**

votes

**1**answer

102 views

### Vertex-connectivity of connected, vertex-transitive graphs without $K_4$ is maximum possible

A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. ...

**0**

votes

**1**answer

39 views

### Number of $k$-walks containing a vertex in an unweighted multigraph

Let $G = (V,E,W)$ be a weighted graph, where each edge $e = (v_i,v_j)$ has weight $w_{ij} \in \mathbb Z^+ \cup \{0\}$. By replacing $e$ with $w_{ij}$ copies of unweighted multiedges, a weighted graph ...

**2**

votes

**3**answers

206 views

### Making integer multisets graphic

Let $M=(X,f)$ be a multiset, where $X$ is the underlying set of elements and $f:X\rightarrow\mathbb{N}$ is the multiplicity function. For every $k\in\mathbb{N}$ put $k\cdot M:=(X,k\cdot f)$. It is ...

**19**

votes

**0**answers

307 views

### Zero curves of Tutte Polynomials?

There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a ...

**1**

vote

**2**answers

72 views

### Position likelihood in a 2D graph [closed]

I am looking for general principles or specific answers to this generic example.
Assume a 2d grid with no boundaries and a roving dot (ant/drunk guy/particle) that is initially located at some ...

**4**

votes

**0**answers

71 views

### A relaxation of proper coloring

I am wondering if the following relaxation of proper coloring appears somewhere. I have tried some searching and have found a few relaxations of proper coloring, but none the coincides with what I ...

**6**

votes

**2**answers

262 views

### extremal bipartite graph

I'm facing the following question:
Given a bipartite graph $G = (L \cup R, E)$.
Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$.
What is a minimal possible number ...

**4**

votes

**1**answer

86 views

### $k$-planar graphs and genus

Is there a simple function that connects $k$ in $k$-planar graphs and genus of such graphs?
If there is no simple function is there any non-trivial upper and lower bound?

**3**

votes

**0**answers

78 views

### Group Travel Salesman Problem

For the following Group Traveling Salesman problem, I'd like to know if there exists some poly-time approximation algorithm with constant approximation factor.
Group TSP is defined as follows: Take a ...

**7**

votes

**2**answers

241 views

### A Different 2-factor in a graph

We know that a k-factor of G is a k-regular spanning subgraph of G. And if G is 4-regular (or 2k-regular), it can be partitioned into 2 (k) edge-disjoint 2-factors (Petersen 1891).
My question is in ...

**-1**

votes

**2**answers

73 views

### Is there a formula that determines the size of the leafage of a graph's spanning tree? [closed]

In general terms, all the spanning trees of a graph G have the same number of leaves.
Is there any formula that allows us to know the number of leaves in terms of |V| and |E| for any spanning tree of ...

**0**

votes

**2**answers

106 views

### Infinite k-connected planar graphs

By planar I mean there is no $K_{3,3}$ minor of $K_5$ minor. Also, I am only considering the $\mathbb{R}^2$ surface, not a torus not any other surfaces.
I know that to construct such graph, For $k ...

**2**

votes

**1**answer

130 views

### Does this version of Hadwiger's conjecture hold for graphs with infinite chromatic number?

Let $G = (V,E)$ be a finite, simple, undirected graph. Hadwiger's conjecture states that
(Hadw): $K_{\chi(G)}$ is a minor of $G$.
It turns out that for finite graphs, (Hadw) is equivalent to the ...

**2**

votes

**0**answers

51 views

### The numbers of edge colorings and partitions into vertex covers

Let $G = \langle X \cup Y, E\rangle$ be a $d$-regular bipartite graph such that $|U|=|V|=n$, and assume that $d$ divides $n$. Let $F(G)$ denote the number of proper edge colorings of $G$ using $d$ ...

**-1**

votes

**1**answer

106 views

### Graph such that edge contraction increases chromatic number

Let $G=(V,E)$ be a simple, undirected graph with the following properties:
Contracting any edge increases the chromatic number by $1$;
For each minor $M$ of $G$ we have $\chi(M) \leq \chi(G) + 1$.
...

**1**

vote

**1**answer

109 views

### Simple Graphs and Automorphisms of the Hypercube

Consider the set $\mathcal{G}_v$ of all finite simple graphs on a given set of $v$ vertices. Let $m={v\choose 2}$ for sake of notation. Given an identification of $\{1,\dots,m\}$ with the set of ...

**1**

vote

**1**answer

154 views

### How to uniquely define a tree? [closed]

In an undirected unlabled graph $G=(V,E)$, we want to find a tree as a subgraph, such that the graph can be decomposed into edge disjoint trees(all the tress are isomorphic). How to define such a tree ...

**1**

vote

**1**answer

73 views

### Probability of paths to the boundary of a tree

Let $G_n$ be the $4$-regular tree of depth $n$, that is to say the finite graph given by the ball of radius $n$ in the Cayley graph of the free group on two generators. By the root I mean the vertex ...

**2**

votes

**1**answer

102 views

### VLSI circuit embeddings

In the following paper by Valiant
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
He shows under theorem 2 (at the bottom of the second page) that any planar graph $G$ of degree 3 or 4 ...

**3**

votes

**0**answers

119 views

### Edit distance vs. canonical adjacency matrix distance

Let $G$ and $G'$ be two simple random graphs on the same set of nodes. Let $d_{edit}$ be the edit distance between $G$ and $G'$. Let $\mathbf{A}$ and $\mathbf{A'}$ be the adjacency matrices of the ...

**6**

votes

**1**answer

315 views

### Graphs in which any two odd cycle have a common vertex

Let $G$ be a graph in which any two odd cycles have a common vertex. It is easy to see that $\chi(G)\leq 5$ (choose minimal odd cycle $C$, use two colors for $G\setminus C$ and three colors for $C$). ...

**0**

votes

**0**answers

105 views

### Is there any result on the homomorphic images of hypercube graphs?

Let $Q_n$ be a hypercube graph and $\phi: Q_n\to G$ a surjective simplicial graph morphism i.e. if $u,v$ are adjacent vertices in $Q_n$ then either $\phi(u)=\phi(v)$ or $\phi(u),\phi(v)$ are adjacent. ...

**6**

votes

**1**answer

217 views

### Graph with group structure?

Is there any established theory of graphs which themselves are groups? I don't mean Cayley graphs or "graphs of groups". I mean a graph whose set of vertices forms a group, where the group operation ...

**3**

votes

**1**answer

200 views

### Planarity of infinite graphs

Let $G$ be a graph with disjoint copies of $K_{1,3}$. Prove that if there are uncountably many copies of $K_{1,3}$ in $G$, then $G$ is not planar.
I have a proof of this statement by ...

**7**

votes

**1**answer

272 views

### Chromatic numbers of nowhere dense graphs

Given $c\in (0,1)$ and a graph $G=(V,E)$ such that any subset $U\subset V$ contains an independent subset of cardinality at least $c|U|$. Does it allow to bound the chromatic number $\chi(G)$ by the ...

**16**

votes

**0**answers

264 views

### Simpler proofs of certain Ramsey numbers

The reason for the gorgeous simplicity of the classic proofs of $R(3,3)$, $R(4,4)$, $R(3,4)$ and $R(3,5)$ is that essentially all you need is the trivial bound and a picture.
But for bigger Ramsey ...

**4**

votes

**0**answers

78 views

### Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...

**11**

votes

**1**answer

220 views

### What is the chromatic number of the “conic hypergraph” on a non-singular plane cubic?

Can we color the points of a complex non-singular plane cubic curve with finitely many colors so that no conic intersects the curve at 6 distinct points of the same color?
If so, what is the smallest ...

**6**

votes

**2**answers

130 views

### Critical with respect to chromatic, but not Hadwiger number

For any simple, undirected graph $G=(V,E)$ where $V$ is finite, we define the Hadwiger number $\eta(G)$ to be the maximum $n$ such that $K_n$ is a minor of $G$.
Is there a graph $G$ on such that ...

**3**

votes

**2**answers

63 views

### Is there an algorithm for generating sets of routes that satisfy edge volume constraints?

I have reduced a problem I'm working on to something resembling a graph theory problem, and my limited intuition tells me that it's not so esoteric that only I could have ever considered it. I'm ...

**1**

vote

**2**answers

56 views

### Maximum subgraph edge distance greater than given number

I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the ...

**2**

votes

**1**answer

51 views

### Simple decomposition of $K_{2n}-I$ into hamiltonian cycles

http://mathworld.wolfram.com/HamiltonDecomposition.html
In the 1890s, Walecki showed that complete graphs K_n admit a Hamilton decomposition for odd n, and decompositions into Hamiltonian cycles ...

**8**

votes

**0**answers

130 views

### Edge-colorings of plane graphs: do you know references where the following questions are studied?

Let $G$ be a plane graph (or more generally, a graph embedded on a surface) with a proper edge-coloring of $G$ with $k$ colors $\{1,\ldots,k\}$. I am interested in studying the cyclic permutations of ...

**-2**

votes

**1**answer

86 views

### Graphs such that contracting an edge decreases the chromatic number [closed]

Let $G = (V,E)$ be a finite, simple, undirected, connected graph, such that contracting an edge reduces the chromatic number. Does this imply that $G$ is complete?

**2**

votes

**1**answer

163 views

### Is there anything similar to the four color theorem for 3-dimensional objects?

From Wikipedia:
In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more ...

**5**

votes

**1**answer

141 views

### Closeness graph of a topological space

Let $(X,\tau)$ be a topological space. We say that $x, y \in X$ are close if for every neighborhood $U$ of $x$ and $V$ of $y$ we have $U\cap V \neq \emptyset$. Let $E$ be the set of $\{x,y\}$ where ...

**7**

votes

**1**answer

258 views

### A matching that covers vertices with maximum degree

We have a graph G with maximum degree $\Delta$. The induced subgraph on vertices with degree equal to $\Delta$ is a bipartite graph (while the original graph is not).
Prove that G has a matching that ...

**-1**

votes

**1**answer

81 views

### Shortest path problem [closed]

Say that $G'$ is a graph re-weighted from $G$ using the rule: $w'
(u, v) = w(u, v) − f(u) + f(v)$, where $f$ always produce the positive results for any nodes. Can we prove
that the shortest path ...

**7**

votes

**0**answers

65 views

### Are graphs with sparse $r$-balls necessarily sparse?

Let $G$ be an unweighted undirected graph with the following property:
For some integer $r$, for all nodes $v$, we have
$$\frac{\sum \limits_{u \in B(v, r)} \deg(u)}{|B(v, r)|} \le D$$
where $B(v, r) ...

**1**

vote

**0**answers

106 views

### Hashimoto Matrix (Non-backtracking operator) and the Graph Laplacian

The question is: how can we recover the graph Laplacian or its spectrum from the Hashimoto Matrix (also commonly called the Non-backtracking operator)?
To make the question as self-contained as ...

**7**

votes

**4**answers

258 views

### Graph homomorphisms and line graph

If $G,H$ are simple, undirected graphs, we say that they are in a hom(omorphism)-relation if there is a graph homomorphism from $G$ to $H$ or from $H$ to $G$.
For any graph $G$ let $L(G)$ denote its ...

**6**

votes

**1**answer

197 views

### Given k, what is the minimum n such that n choose n/2 is greater than k? [closed]

I'm not an expert in combinatorics, but it sometimes comes up in my research with students in computer science (which is already pretty far away from my speciality of abstract homotopy theory). I just ...

**7**

votes

**0**answers

125 views

### De Bruijn sequence inside De Bruijn sequence

A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1a_2\ldots a_{2^n}$, with $a_i∈\{0,1\}$, and such that each of the $2^n$ binary $n$-tuples occurs exactly once in $S$.
What is ...

**5**

votes

**2**answers

207 views

### How can I prove that these two graph coloring problems are polynomial time equivalent?

Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$.
...

**3**

votes

**0**answers

102 views

### Synonyms for “labeling” of a graph

In Preprint 1 we write numerical labels 0 or 1 at each vertex of a Dynkin diagram $D$. We call it a labeling of the graph (Dynkin diagram) $D$.
In Preprint 2 we consider an extended (affine) Dynkin ...