**-2**

votes

**0**answers

21 views

### Perfect matching in a graph [on hold]

Is it true, that in every 2-regular graph with 14 vertices there is a perfect matching ? If you think it's true - prove it, otherwise show counter-example
this is my excercise. I think that it's true ...

**1**

vote

**1**answer

273 views

### Modern books about orders and algebras on trees

Please help to find books about orders and algebras on trees.
If there is no modern books, please advice good old ones!
I'm more interested in finite trees (my current problem), but infinite ones are ...

**0**

votes

**0**answers

23 views

### Complexity of edge coloring graphs of sufficiently large maximum degree

I am interested in the complexity of edge coloring
graphs with $\Delta(G) > |V(G)|/3$.
This is closely related to the Overfull conjecture (OC).
Conjecture/Question: If a simple graph G with n ...

**21**

votes

**2**answers

354 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...

**2**

votes

**1**answer

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

**2**

votes

**1**answer

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

**4**

votes

**0**answers

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

**-1**

votes

**1**answer

66 views

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

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?

**5**

votes

**1**answer

110 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

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

**10**

votes

**1**answer

421 views

### Travelling Salesman Problem: Can the nearest neighbor algorithm be $n$ times longer than the optimal solution?

This is inspired by a recent question.
Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the ...

**-2**

votes

**0**answers

54 views

### Maximally nonplanar graphs [closed]

Is there any way to characterize maximally non-planar graphs?
For example, given a random collection of k-regular graphs, there is a clear distinction between the planar and non-planar graphs by ...

**19**

votes

**3**answers

2k views

### What is this subgroup of $\mathfrak S_{12}$?

On some occasion I was gifted a calendar. It displays a math quizz every day of the year. Not really exciting in general, but at least one of them let me raise a group-theoretic question.
The quizz: ...

**-2**

votes

**1**answer

69 views

### Shortest path problem [on hold]

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

**3**answers

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

**5**

votes

**0**answers

54 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

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

**9**

votes

**1**answer

505 views

### Bicycles and spanning trees of graphs

A spanning tree in a graph is a connected spanning subgraph with no cycles; it is well known that the number of spanning trees can be found by taking the determinant of a certain matrix related to the ...

**6**

votes

**1**answer

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

**6**

votes

**1**answer

487 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**7**

votes

**0**answers

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

**6**

votes

**1**answer

325 views

### Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$
such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...

**3**

votes

**0**answers

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

**5**

votes

**1**answer

125 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$.
...

**7**

votes

**3**answers

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

**0**

votes

**1**answer

223 views

### Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$).
The cost to send $x$ unit of flow through edge $e_i$ is defined ...

**3**

votes

**0**answers

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

**15**

votes

**4**answers

648 views

### What algebraic structures are related to the McGee graph?

Recall that an $(n,g)$-graph is a simple graph where each node has $n$ neighbors and the shortest cycle has length $g$, while an $(n,g)$-cage is $(n,g)$-graph with the minimum number of nodes.
The ...

**3**

votes

**1**answer

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

**1**

vote

**2**answers

5k views

### Maximum number of edges in a planar graph

What is the maximum number of edges a planar subgraph of $K_n$ can have? Is there a simple way to calculate this if not, are there some values of n for which this is easier to find out?

**2**

votes

**1**answer

177 views

### inequality with exponents

We are given a graph $G$, each vertex $v$ has an assigned value $\gamma_v\in [0,1]$, and it happens that for every $v$ we have $\gamma_v+\sum_{u\in \delta(v)} \gamma_u = 1$. Assume that $\sum_v ...

**1**

vote

**2**answers

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

**6**

votes

**1**answer

117 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

**0**answers

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

**-1**

votes

**1**answer

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

**6**

votes

**2**answers

104 views

### Class of hypergraphs that are always the neighborhood hypergraph of some simple graph

Let $G=(V,E)$ be a graph. Its (open) neighborhood hypergraph $\mathcal{H}(G)$ has the same vertex set $V$ with a hyperedge for the (open) neighborhood of every vertex $v \in V$.
It seems that not ...

**2**

votes

**1**answer

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

**4**

votes

**1**answer

167 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?
...

**0**

votes

**1**answer

212 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...

**40**

votes

**12**answers

4k views

### Generalizations of the Four-Color theorem

The four color theorem asserts that every planar graph can be properly colored by four colors.
The purpose of this question is to collect generalizations, variations, and strengthenings of the four ...

**1**

vote

**1**answer

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

**1**

vote

**2**answers

131 views

### Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties:
The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it).
$T$ has a ...

**1**

vote

**2**answers

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

**6**

votes

**1**answer

82 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

**0**answers

65 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)$ ...

**6**

votes

**1**answer

370 views

### How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.
A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...

**3**

votes

**0**answers

56 views

### Small degree vertices in an epsilon-tough graph

We say that a graph is t-tough if by deleting a set if vertices $S$, the resulting graph will have at most $|S|/t$ connected components. We say that a graph is minimally t-tough if the deletion of an ...

**1**

vote

**1**answer

134 views

### Number of nodes in a given distance in (random) regular graph

Given a d-regular graph $G=<V,E>$ (connected, unweighted & simple), and a node $v$.
denote all nodes with distance $k$ from $v$ $$L_k=\{u\in V : dis(v,u) = k\}$$
Let's call it "the k-th ...

**0**

votes

**1**answer

119 views

### Reference request: Strong Connectivity and the Incidence Matrix

Question: What would be a good reference for characterizations of strong connectivity of a digraph in terms of its incidence matrix?
Details: Consider a digraph $(V, E)$ with vertex set
$$V = ...

**33**

votes

**5**answers

4k views

### Algebraic Proof of 4-Colour Theorem?

4-Colour Theorem. Every planar graph is 4-colourable.
This theorem of course has a well-known history. It was first proven by Appel and Haken in 1976, but their proof was met with skepticism ...