Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, ...

learn more… | top users | synonyms

1
vote
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
3answers
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
1answer
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
2answers
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
2answers
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 ...