**3**

votes

**0**answers

68 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

207 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

71 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

95 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

127 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

100 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

93 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

147 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

67 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

98 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 ...

**1**

vote

**0**answers

96 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

287 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

102 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

212 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

186 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

265 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

250 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

75 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

216 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

129 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

58 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

50 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

43 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

128 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

81 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

157 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

137 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

191 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

78 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

64 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

89 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

249 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

182 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

122 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

191 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

101 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 ...

**3**

votes

**0**answers

74 views

### The degree/diameter problem for even girth graphs starting with upper bound

I posted this on stackexchange but due to a lack of response there I am posting here.
Let $G$ be a graph with girth $g$, minimal degree $\delta$, maximal degree $\Delta$, and diameter $D$. Define ...

**3**

votes

**1**answer

87 views

### Construction of planar embedding

I'm reading the following paper on universality considerations in VLSI circuits
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In Theorem 2 On the second page it states there exists ...

**7**

votes

**3**answers

215 views

### Embedding planar graphs into the grid

I've seen the following lemma in a paper. The result is by Valiant.
A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**6**

votes

**1**answer

133 views

### Refinement of Dirac's theorem on Hamiltonian graphs

Dirac's theorem states that if degree of each vertex of a graph $G=(V,E)$ is not less than $|V|/2$, then it has Hamiltonian cycle. It is less known, but still known and not so hard to prove (though I ...

**2**

votes

**2**answers

161 views

### SVD vs Fourier analysis for data.

Fourier analysis is useful for analysis in the frequency domain. SVD on the other hand is useful for analysis of data, and expressing noise in the data. I have a problem that needs extensive data ...

**0**

votes

**1**answer

61 views

### Different graphs with the same open neighborhood hypergraph

For any set $X$ we let $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$.
Let $G=(V,E)$ be a simple, undirected graph. Its open neighborhood hypergraph $\mathcal{H}(G)$ has the same vertex set $V$ with a ...

**2**

votes

**1**answer

84 views

### First passage percolation for general graphs

There have been many questions about the behavior of first-passage percolation on specific graphs. In particular, it seems like cliques, grids, random graphs, and ladders are well-studied. But I can't ...

**1**

vote

**1**answer

59 views

### The existence of a specific partition of the edge set of $K_{2n}$

Let $n$ be an even positive integer and $K_{2n}$ be the complete graph on $2n$ vertices. There are $\dfrac{1}{2}{{2n}\choose n}={{2n-1}\choose n}$ subgraphs of $K_{2n}$ which is isomorphic to ...

**2**

votes

**0**answers

275 views

### Maps between graphs defined through laplacian operations

Edit: The views/answers ratio on this question tells me that it was too long. As such, I've stripped out examples and now ask the question in brief. For examples, please ask in the comments or look at ...

**6**

votes

**1**answer

87 views

### Above/below directed graph on cells of arrangement of lines

This question concerns the structure of a directed graph
built on the cells of an arrangement of lines.
My basic question is whether this graph has been
studied before, perhaps in another guise. I ...

**1**

vote

**2**answers

95 views

### Application of cospectral graphs

Cospectral graphs are graphs having same eigenvalues. Constructions of cospectral graph is an interesting question in graph theory. Now a days we use graph theory in different brunches of Sciences and ...

**1**

vote

**0**answers

71 views

### Computing the Edge Chromatic Polynomial of a graph

Is there a recursive formulae to compute the edge chromatic polynomial of a graph?
The following formulae is known for the vertex chromatic polynomial of a grapg $G$
$P(G,x)=P(G-uv, x)- P(G/uv,x)$ ...

**4**

votes

**1**answer

191 views

### Counting trees according to endpoints

Question: Is there a nice (or any) formula for the generating function
$$T(x,y) = \sum_{m,n} t_{m,n} x^my^n,$$
where $t_{m,n}$ is the number of trees with $m$ vertices and $n$ endpoints?
...