**1**

vote

**0**answers

17 views

### Path Sums in Arc Labeled st-graphs

My research has led me to a question on sums of integer labeled arc paths in an st-graph (single source single sink, acyclic, I actually have multi-graphs). The problem is to label all the arcs in a ...

**7**

votes

**0**answers

75 views

### A separation property of graphs of bounded tree-width

The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2)
Let $T$ be a tree and $r, m$ ...

**0**

votes

**0**answers

20 views

### A Statement about a General Property of Negative Cycle Detection Algorithms

in this paper from 1999, the authors Boris Cherkassky and Andrew Goldberg state in the abstract that
"The negative cycle problem is to find a negative length cycle in a network or to prove that ...

**0**

votes

**1**answer

48 views

### Cycle-intersecting subsets

Let $G=(V,E)$ be a finite, simple, undirected graph. We call $D\subseteq V$ cycle-intersecting if for every simple cycle $C\subseteq V$ we have $C\cap D \neq \emptyset$.
Is there a graph $G$ such ...

**0**

votes

**1**answer

57 views

### What is the definition of size of an edge$?$

In page-$13$ of Graph minors. $X$. Obstructions to tree-decomposition, $\gamma(G)$ introduced as maximum size of an edge. What is the definition of size of an edge$?$ I think it may be number of edges ...

**3**

votes

**1**answer

59 views

### What is the relation between Treewidth and Order of graph?

Can we say in general, Treewidth of every graph is less than or equal to number of vertices in that graph?
Is there any other general relation between Treewidth and Order of graphs?

**2**

votes

**1**answer

47 views

### What is the relation between Hadwiger number and Treewidth?

Is there any general relation between Hadwiger number and Treewidth of a graph? Intuitively I think Hadwiger number is greater than or equal to Treewidth, but I couldn't prove it.

**4**

votes

**1**answer

121 views

### Which graphs are prime under the Cartesian product?

I'm looking for a characterization of graphs that are prime under the Cartesian product, with prime defined as in this question. Does such a characterization exist, either in general or after ...

**4**

votes

**1**answer

123 views

### does every vertex-cut set in a maximal planar graph contain a cycle?

$G = (V, E)$ is a 3-connected plane triangulation. Let $S \subset V$ such that $G(V - S)$ is disconnected. Is it true that $G(S)$ must contains a separating cycle?
My intuition is leading me to ...

**1**

vote

**1**answer

73 views

### What is the relation between size of maximum clique and branchwidth?

Let $bw(G)$ be the branchwidth of graph $G$ and $\omega(G)$ be the size of maximum clique in $G$. I think the following inequality holds:
$$
\omega(G)\leq bw(G)
$$
Intuition: Assume (in reverse of ...

**0**

votes

**0**answers

42 views

### Arithmetic progressions on a graph

Given $K_k$ a complete graph what is the minimum $n\in\Bbb N$ needed so that there is a map:
$$f:\{0,1,\dots,n\}\rightarrow\mathsf{Edges}(K_k)$$ which makes every simple cycle to be $r$-term ...

**0**

votes

**0**answers

88 views

### Variance of the average path length of connected graphs

The average path length has been defined for a connected graph $G$. It is defined here:
https://en.wikipedia.org/wiki/Average_path_length
Has the variance of these path lengths ever been ...

**0**

votes

**0**answers

62 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

50 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

77 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

154 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

100 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

180 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

163 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

339 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

122 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

105 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

586 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

87 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

315 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

72 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

73 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

80 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

86 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

500 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

153 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

169 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

189 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

160 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

203 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

40 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

103 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

55 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

59 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

89 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

62 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

131 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

164 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

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

**52**

votes

**3**answers

4k 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

136 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

83 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

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