**0**

votes

**0**answers

61 views

### Almost-hypohamiltonian Kneser Graphs

Here, it states that:
When $n\ge 3k$, the Kneser graph $KG_{n,k}$ always contains a Hamiltonian cycle. Computational searches have found that all connected Kneser graphs for $n \le 27,$ except for ...

**1**

vote

**0**answers

46 views

### How effective is using local property to test Shannon capacity?

A key tool in graph theory is the laplacian which is a local property. We can form a semidefinite programming and get an upper bound for Shannon capacity using laplacian.
Shannon capacity is ...

**2**

votes

**1**answer

68 views

### Repeated nodes in tree-decomposition of a graph is allowed or not?

As we know, a tree-decomposition of a graph must have following features:
All vertices are covered
All edges are covered
The connectivity condition
I think using repeated nodes in ...

**1**

vote

**1**answer

103 views

### $q$-connectedness of random digraphs obtained from a fixed graph

Let $G = (E,V)$ be an undirected graph (which can have multiple edges or loops).
Let $k,l,m\colon E\to \mathbb{R}_{\geq 0}$ be three edge-weight functions that satisfy $2k(e) + l(e) + m(e) = 1$ for ...

**-2**

votes

**1**answer

152 views

### Planar Graphs with #Vertices = #Faces [closed]

Do you know anything special about that kind of planar graphs? An article that covers these graphs might be helpful.

**3**

votes

**0**answers

96 views

### Construction of algebraic curves using line bundles on graphs

In this paper http://arxiv.org/abs/0707.1309 Matthew Baker and Serguei Norine, construct a analogue of the Riemman Roch formula for Lineal Systems defined on graphs. In the paper ...

**1**

vote

**1**answer

168 views

### On Knot Equivalence problem statement

How is the knot equivalence problem represented?
By this I mean I am looking for an analogy that compares with graph equivalence. For graph equivalence, we have two graphs $G_1$ and $G_2$ with ...

**1**

vote

**0**answers

156 views

### Concrete solution to the (oriented) Oberwolfach problem with one table

I asked the following on MSE, but it received little attention...
The oriented Oberwolfach problem (with only one table) and its solution are the following.
In a meeting of $n$ people during $n-1$ ...

**6**

votes

**1**answer

325 views

### How many non-isomorphic graphs of 50 vertices and 150 edges

Is there an way to estimate (if not calculate) the number of possible non-isomorphic graphs of 50 vertices and 150 edges?

**3**

votes

**0**answers

120 views

### In a random graph which one is more probable, $k$-clique or $k$-core?

Recall that the $k$-core of a graph $G$ is the unique maximal subgraph of $G$ with minimum degree at least $k$.
In an Erdos-Renyi random graph, where the edge selection is independent with ...

**-1**

votes

**2**answers

96 views

### connected and vertex-transitive prime graphs with respect to Cartesian product

A graph $\Gamma$ is called prime with respect to the Cartesian product if
$\Gamma=\Gamma_1\square\Gamma_2$ implies that $\Gamma_1=K_1$ or $\Gamma_2=K_1$, where $\square$ denote the Cartesian product.
...

**3**

votes

**1**answer

543 views

### A generalized theorem of Hall's marriage theorem

We all know Hall's marriage theorem as following:
A bipartite graph $G$ with bipartition $\{ A,B \}$ contains a matching of $A$ if and only if $|N(S)|\geq |S|$ for all $S\subseteq A$.
And I am ...

**0**

votes

**1**answer

83 views

### Maximal induced cycles on $n$-clique graphs

For any set $X$ we set $[X]^2 = \big\{\{a,b\}: a, b\in X\text{ and } a\neq b\big\}$.
We say a simple undirected graph $G=(V,E)$ is an $n$-clique graph if there are $S_1,\ldots,S_n\subseteq V$ such ...

**14**

votes

**1**answer

292 views

### Convergence rate of Fagin's 0-1 law for first-order properties of random graphs

Fagin's 0-1 law for first-order properties of random graphs states that, for every first-order sentence in the logic of graphs, the probability that a uniformly random $n$-vertex graph models the ...

**5**

votes

**0**answers

64 views

### Chromatic numbers for coloring-constrained graphs

I am interested in any and all articles about chromatic numbers applying to constrained colorings of a graph. For example, if a graph must be (properly) colored so that there is a 2-color path ...

**2**

votes

**0**answers

57 views

### Planar triangulations for which all distinct 4-colorings consist of exactly 6 Kempe chains

Are there any internally 6-connected planar triangulations other than the icosahedron all of whose distinct 4-colorings consist of exactly 6 Kempe chains, one for each of the 6 color-pairs?
Addendum: ...

**4**

votes

**1**answer

71 views

### Show existence maximal clique of order $s$ in an multigraph where each vertex is colored with a set of colors

You are given a multigraph $G$ with $n$ vertices as follows:
$V := (v_1, v_2, \dots ,v_n)$
$C := \{c_1, c_2, \dots\}$, be an infinite set of colors.
$f: V \rightarrow \mathbb{P}_{\le m}(C) $, a ...

**2**

votes

**1**answer

77 views

### Partitioning the vertex set of a planar bipartite graph into a tree and an independent set

Let $G = (V, E)$ be a planar bipartite graph such that there is a partition $(V1, V2)$ of $V$ where $V1$ induces a tree and $V2$ induces an independent set.
Is there a characterization of such ...

**0**

votes

**1**answer

71 views

### Maximal chromatic number with a fixed number of edges

Given a graph $G$ with $m$ edges, what is the maximum chromatic number $\chi(G)$ that the graph can have?
My guess is that $\chi(G) \leq r(m)$ where $r(m) := \max\{k\in \mathbb{N}:
\frac{k(k-1)}{2} ...

**27**

votes

**0**answers

470 views

### What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation:
$$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$
$a$ is an ...

**8**

votes

**1**answer

141 views

### Equalizing Geometric means of Graph Cycles

Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are ...

**1**

vote

**1**answer

140 views

### Sum of Eigenvectors Entries of an Adjacency Matrix

I have a question regarding the sums $\sum_{i=1}^{n}v_{j}\left(i\right)$ where $v_j$ are eigenvectors of adjacency matrix $A$ which have been normalized to unit length.
Ordering the eigenvectors by ...

**6**

votes

**1**answer

175 views

### Eigenvalue inequality for regular graphs

I recently proved an inequality relating some of the eigenvalues of a regular graph with each other, and I was wondering if it is already known. I was unable to find it online, and a quick skim ...

**1**

vote

**0**answers

158 views

### A path optimisation problem

Consider a graph of $n$ nodes randomly located in $[0,1]^2$. Each node moves following a path randomly chosen from the set of all possible paths. Regard nodes as attackers. A policeman seeks an ...

**3**

votes

**1**answer

151 views

### Algorithm to count the number of perfect matchings in non planar graph

I need to count the number of perfect matchings of a certain family of graphs. This family of graph is non planar and a type of snark. For the initial cases, it seems that this number is growing ...

**0**

votes

**0**answers

37 views

### Arc-transitive graphs of prime valency with non-solvable automorphism group

Let $\Gamma$ be a $G$-arc-transitive graph of prime valency and $G$ be non-solvable. Is there any classification of such graph?

**-1**

votes

**2**answers

97 views

### Do graphs with $\omega(G) = \chi(G)$ grow “common” as $|V|$ grows large?

On the set $[n]:= \{1,\ldots,n\}$ we consider the set $${\cal P}_2([n]) = \big\{\{a,b\}: a,b \in [n], a\neq b\big\}.$$
Since $$|{\cal P}_2([n])| =2^{n \choose 2}$$ there are exactly $2^{n\choose 2}$ ...

**2**

votes

**1**answer

45 views

### Edge-perspective degree distribution

I was reading this paper when I came across something called the edge-perspective degree distribution in a network. Consider a graph $G$, the degree distribution of whose nodes is $f(d)$. They say the ...

**1**

vote

**1**answer

56 views

### Properties of very well covered graph

Definition: Very well covered graph to be a well-covered graph (possibly disconnected, but with no isolated vertices) in which each
maximal independent set (and therefore also each minimal ...

**3**

votes

**1**answer

85 views

### Is there any vertex-transitive non-Cayley graph with 24 vertices and valency 5?

I know that, by D. McKay and C. E. Praeger papers" Vertex-transitive graphs which are not Cayley graphs I", there exist 112 non-Cayley vertex-transitive graph with 24 vertices.
Is there any such ...

**0**

votes

**1**answer

60 views

### Weak Erdos graphs

We call a finite, simple, undirected graph $G=(V,E)$ an $n$-Erdos graph if there are $n$ subsets $S_1,\ldots, S_n$ of $V$ such that
$V = \bigcup_{n=1}^n S_n$;
each $S_k$ has $n$ elements for ...

**1**

vote

**1**answer

114 views

### Node-edge coloring of graphs

There must be work on this concept, but I am not finding it through
searches, perhaps using the wrong terminology.
Define a node-edge coloring of a graph ...

**12**

votes

**1**answer

157 views

### Graphs with a coloring that majorizes all other colorings

By a coloring of a graph $G = (V,E)$ I mean a map $\kappa:V\to\mathbb{N}$ such that $\kappa(u)\ne \kappa(v)$ whenever $u$ and $v$ are adjacent. (Sometimes this is called a proper coloring but I am ...

**1**

vote

**0**answers

79 views

### A version of the Weak Regularity Lemma

Definitions: Given a graph $G$ and $S$, $T \subseteq V(G)$, let $e_G(S, T)$ denote the number of edges of $G$ with one endpoint in $S$ and the other in $T$ and let
$$d_G(S, T) := \frac{e_G(S, ...

**48**

votes

**3**answers

3k views

### What are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?

This week, news came out that Laszlo Babai has found a quasi-polynomial time algorithm to solve the Graph Isomorphism problem (that is: $O(\exp(polylog(n)))$). He is giving a series of talks this ...

**1**

vote

**1**answer

129 views

### Uniquely describing a graph

According to answers here http://math.stackexchange.com/questions/1524598/a-general-incidence-problem// an unigraph comes from unigraphic degree sequences if it can be uniquely determined by its ...

**2**

votes

**2**answers

74 views

### A question about a specific partition of a graph

Let $G=(V,E)$ be a graph and $V=A\cup B$ satisfying
$(1)A\cap B=\emptyset;$
$(2)|N_G(v)\cap B|\geq |N_G(v)\cap A|,\forall v\in A$ and $|N_G(v)\cap A|\geq |N_G(v)\cap B|,\forall v\in B$.
Let ...

**11**

votes

**2**answers

349 views

### Pursuit-Evasion type game on graph (“Flyswatter game”)

An instance of the "flyswatter game" is defined by a graph $G$ and positive integer $k$. There are two players, A (the 'fly') and B (the 'swatter'). Essentially, the fly moves around $G$ and the ...

**0**

votes

**0**answers

91 views

### Does anyone know any applications of CW-complexes in graph theory?

As everyone knows :P, a graph is a CW-complex of dimension 1. Knowing that, are there any interesting results in graph theory that arise from working with CW-complexes? And more specifically, in ...

**0**

votes

**1**answer

76 views

### The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$).
This is what I observed from some books (e.g. "Combinatorial ...

**3**

votes

**1**answer

78 views

### Probabilistic many-to-one matching

Let $p<1$ be a constant. Consider two sets $A,B$ with $n$ and $nf(n)$ vertices, respectively, where $f(n)$ is an integer. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears ...

**1**

vote

**1**answer

119 views

### Two types of random walkers on square lattice

Consider a two dimensional square lattice ($n$ by $n$), which is our space $S$ (each point labelled by an index $1\to n^2$), containing two types of particles, distinguished here by either an index ...

**2**

votes

**2**answers

129 views

### Matching with probabilistic edges

Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...

**4**

votes

**2**answers

170 views

### Volume of the convex hull of the set of all graphic sequences of a given length

Consider the set of all graphic sequences with $n$ elements as a subset of $\mathbb{R}^{n}$, namely let
$$D(n)=\{(d_{1},\dots,d_{n})\in\mathbb{Z}_{+}^{n}:d_{1}\geq\dots\geq d_{n},\ ...

**1**

vote

**1**answer

94 views

### Eulerian graphs with prescribed number of edges

Under what conditions there exists an $n$-vertex eulerian graph with $m$ edges for $1\leq m\leq\frac{n(n-1)}{2}$?

**8**

votes

**1**answer

173 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

256 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

22 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, ...