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

0
votes
0answers
31 views

Does the Ruzsa-Szemeredi Theorem also capture graphs decomposable into *nearly* induced matchings?

The well-known Ruzsa-Szemeredi Theorem states that a graph whose edges can be partitioned into $n$ induced matchings has at most $\frac{n^2}{RS(n)}$ edges, for some slow-growing function $RS(n)$. Now,...
2
votes
0answers
60 views

a continuous analogue of a graph theory question

I am reading a paper and it mentions a continuous analogue of a related graph theory question that people concern. The question is that suppose $E\subset Q=[0,1]^2$ has lebesgue measure $|E|>0$, is ...
0
votes
0answers
36 views

Simple Arrangements of Chords Have Hamiltonian Circuits? [on hold]

An arrangement of $s$ chords are drawn over a circle so that no three chords intersect at a common point and no two chords are parallel. Denote the arrangement by $\mathcal{H}_{s}$. I want to prove ...
2
votes
0answers
35 views

A generalization of the definition of edge coloring and a related problem

A generalization of the definition of edge coloring: For any positive integer $k\geq 2$, a $k$-path edge coloring of a graph $G$ is a assignment of colors to the edges of $G$ so that for every path $...
0
votes
1answer
75 views

Is there currently a known way to construct an injective mapping that transforms finite graphs into discrete geometric objects? [on hold]

If there is such a mapping, it seems as though it could turn the graph isomorphism problem from a purely combinatorial problem to a discrete geometric one.
0
votes
0answers
22 views

Permutation Invariant Color Class

$G$ is a $d$ regular graph, it has $n$ vertices. $S_n$ acts on $n$ vertices of graph $G$. Question: Does there exist a coloring algorithm for which color classes is invariant under all ...
0
votes
0answers
95 views

graduate study in graph theory and combinatorics in canada [on hold]

I'm looking for any graduate programs related to graph theory or combinatorics in canada like in waterloo or simon fraser universities. any other suggestions?
4
votes
1answer
194 views

Number of walks on integer lattice with self-edge at zero

Consider the graph with vertices $V=\mathbb Z$ and edges $$E=\{(n,n+1):n\in\mathbb Z\}\cup\{(0,0)\},$$ that is, the usual integer lattice with a self-edge at zero. For some fixed parameters $a,b,n\in\...
0
votes
1answer
48 views

Bondy and Simonovits Proof for Small Graphs

In their paper, Cycles of Even Length in Graphs (http://renyi.hu/~miki/BondySimEven.pdf), Bondy and Simonovits prove that if a graph $G^n$ has $n$ vertices and at least $100kn^{1+1/k}$ edges then $G^n$...
2
votes
0answers
50 views
+50

How are Polynomials of Toric ideals Studied with Exponents as ST-cuts?

Topic: Toric ideals on Expected value of Structure Functions in Random Graphs Goal: to understand the toric ideal where the exponents $h_i$ and $s_j$ are st-vertex-cuts of a digraph \begin{equation} ...
8
votes
3answers
531 views

Is there a 2-connected k-regular graph without Hamiltonian path?

In this paper (Construction 2.6 p860) the authors have built examples of connected $k$-regular graph without Hamiltonian path, but with a cut-vertex (i.e. it is not $2$-connected). Question: Is ...
1
vote
1answer
66 views
+50

Relaxed path decomposition of a graph

Definition Given a directed connected graph $G$ without multiple edges or self loops. We call a final path of $G$ a path ending with a vertex with no successor (the path can not be extended anymore) ...
1
vote
1answer
346 views

Doing graph theory after a thesis in pure mathematics [closed]

I've just went through the 1st year of my PhD in France, it is related to Floer Homology. I didn't know what it was really about at that time, I chosed this subject because I thought it would combine ...
0
votes
0answers
23 views

Example/ Explanation of Weisfeiler-Lehman method

I am trying to read An Optimal Lower Bound on the Number of Variables for Graph Identification. On page 3 (4th paragraph), it is written- It might color vertices and edges implicitly by using $k$-...
3
votes
2answers
271 views

Create a graph with a specified number of spanning trees

I read that one of the current challenging problems in mathematics is constructing a minimal graph with a specified number of spanning trees (say, $k$). However, is there a quick way to create some ...
1
vote
0answers
50 views

Computing subgraph orbits

I have group $G$ acting on a 4-regular 120 node graph $\Gamma$. I want to compute equivalence classes of connected subgraphs of $\Gamma$, where by equivalent I mean in the same orbit. More ...
9
votes
0answers
109 views

Asymptotics of subgraph densities in graphons

In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...
0
votes
0answers
46 views

Intersection Of Valentine Convex Sets

A set X is said to be m-convex , m integer >=2, if for each set of m points at least one of the associated line segments lies in X. A 3-convex set is sometimes also known as Valentine convex after ...
3
votes
1answer
241 views

Comparison nauty vs. bliss of canonical form of bipartite graphs

I need to compute canonical forms of many (~10^6-10^8) vertex-facets incidence graphs of polytope. Two rather big examples I want to consider are the 600-cell with 120 vertices and 600 facets (...
1
vote
1answer
59 views

best known bounds for spectral radius [closed]

There are many bounds for the spectral radius of graphs in terms of no. of vertices, maximum degree, chromatic number etc. I wish to know till date what are the best lower and upper bound for the ...
1
vote
0answers
55 views

Recognizing cubic graphs decomposable into 2-factor with given cycle type

Petersen's theorem states that every cubic, bridgeless graph contains a perfect matching. It implies that the edge set $E$ can be partitioned into a perfect matching and a 2-factor. Determining the ...
0
votes
0answers
32 views

max-flow at max-cost

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
-4
votes
1answer
87 views

Expression for a complex summation involving factorial [closed]

It is known that $\sum_{k = 0}^{n } {n \choose k}(k!) = \lfloor e \cdot n! \rfloor $ But is it known what $\sum_{p = 0}^{n} \sum_{q = 0}^{n - p} {n \choose p}{{n - p} \choose q} p! \cdot q! \cdot (n-p-...
0
votes
0answers
37 views

How to find faces of graph? [duplicate]

I have à planair graph and I want to find an algorithm that will find all of the faces of the graph. Thanks you in advance for your answers.
0
votes
1answer
36 views

Augmention property of matroid along perfect matching

Let M be a matroid of rank k, B a base, X a set of rank rank(X) < k, and P a perfect matching of the complete bipartite graph (X, B). Is it true that there exists an edge (x, b) of P augmenting X (...
3
votes
1answer
103 views

Base decomposition of matroids

I want to find a generalization of the idea that, in a graphic matroid, every base can be decomposed on the stars (edges adjacent to a vertex). For example one could say that a matroid $M$ of rank $k$...
8
votes
1answer
266 views

How many chromatic polynomials of planar maps are there?

Let P(n) be the set of polynomials that can occur as the chromatic polynomial of a planar map with n countries. What is known or conjectured about the growth of |P(n)|? PS: Thanks Gerry and Noam, ...
0
votes
0answers
54 views

Does anyone have a reference for a proof of expansion for this construction?

http://people.seas.harvard.edu/~salil/pseudorandomness/expanders.pdf "Construction 4.26: p-cycles with inverse chords.... The proof of expansion relies on the “Selberg 3/16 Theorem” from number ...
1
vote
1answer
252 views

Expression for summation involving factorial

It is known that $ \sum_{k = 0}^{n} {n \choose k} = 2^n$ and $ \sum_{k = 0}^{n} {n \choose k} (!k)= n!$. But is it known what $ \sum_{k = 0}^{n } {n \choose k}(k!)$ is equal to?
4
votes
0answers
71 views

Existence a class of graphs with special property

In the following, suppose all graphs are simple and finite. For a given graph $G$, we denote its complement by $\overline{G}$. Let $*$ be a binary operation among graphs, such as Cartesian product, ...
0
votes
0answers
137 views

Graph Coloring: Two adjacent vertices share same color

Consider, subgraphs $G_1, G_2,...... G_x$ of graph $G$. Each subgraph has $k$ vertices. Now, Fix subgraph $G_1$ and consider another subgraph $G_k$ where $1 <k \le x$. The edge set ...
0
votes
0answers
37 views

What's the fastest algorithm for computing transitive reduction for a sparse DAG? [migrated]

I know this is a Math site, but if anyone wants to add pseudocode, Javascript-looking pseudocode would be preferred. Edit: looks like this question would be better for math.stackexchange.com. Would ...
3
votes
1answer
55 views

Is transitive reduction for a direct acyclic graph really unique? [closed]

According to Wikipedia, "If a given graph is a finite directed acyclic graph, its transitive reduction is unique" Here is what I think might be a counter-example: Imagine a diamond-shaped DAG where ...
2
votes
0answers
79 views

Isomorphism with fixed number of Permutations [closed]

Suppose, I have a fixed number of permutations for each sub-graph to determine isomorphism of whole graph. Is it possible to determine efficiently ? For example, $G, H$ are isomorphic graphs. For ...
-1
votes
1answer
57 views

A plane graph problem [closed]

Let G be a planar graph, with edges colored red and blue. Show that there is a vertex v such that going round the vertex in a clockwise direction we encountered no more than two change of colors. Has ...
0
votes
0answers
75 views

Generating set of Graph-Automorphism from Direct Product

Notation: $H$ is the adjacency matrix of graph $\mathcal{H}$ . $$H = \begin{bmatrix} H_{(3)} & R_{(3, 2)} & R_{(3,1)} \\ R_{(3,2)} & H_{(2)} & R_{(2,1)} \\ R_{(3,1)} & R_{(2,1)}...
0
votes
0answers
118 views

Closed form solution of a complex recurrence relation

I am looking for a closed form expression for $ST(n, k)$ defined as $$ ST(n, k) = \sum_{s = 0}^{n - k} {{n - k} \choose s} QT( k + s, k + s - 2, k), $$ where $QT( n, m, k)$ is defined by the ...
3
votes
0answers
65 views

Is the chromatic number of the graph of the permutahedron known?

The permutahedron $\Pi_n$ is the polytope that is the convex hull of all permutations of the vector $(1,2,...,n)$. There are many results on its structure, but I couldn't find a result on the ...
7
votes
2answers
198 views

Graphs with prescribed numbers of k-cliques

Let $(a_1,a_2,\dots, a_n)$ be a sequence of non-negative integers. Q. When does there exists a simple graph $G$ such that its number of $k$-cliques is $a_k$ (that is $G$ has $a_1$ vertices, $a_2$ ...
3
votes
1answer
71 views

Triange-free graph and its complement has Lovász number > 3

I found an example by the method in the paper Explicit Ramsey graphs and orthonormal labelings by Noga Alon 1994. The graph is around $10^6$ vertices, anyone knows smaller graph which is Triangle-free ...
1
vote
3answers
122 views

Hadwiger number and minimal degree

Suppose $G$ is a finite simple graph and $\eta(G)$ is the maximal $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$. If $\delta(G)$ is the minimal degree, do we have $\delta(G)\leq\eta(G)$?
1
vote
0answers
21 views

History of the Vertex Disjoint Cycle Cover with Minimal Edgeweight Sum

Questions: who first posed the problem of determining a collection of (directed) cycles, whose edgeweight sum is minimal and, for which each vertex belongs to exactly one of the cycles? who came up ...
-1
votes
1answer
54 views

Hadwiger number of total graph

Let $G=(V,E)$ be a finite, simple, undirected graph, and let $T(G)$ be its total graph. The Hadwiger number $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$. Is there an ...
1
vote
1answer
59 views

Asymptotic formula for average geodesic length on graph?

If $G$ is a finite, connected simple graph then is there an expression for the average geodesic length? That is suppose I know two nodes $n_1$ and $n_2$, the number of edges in my graph and at those ...
-1
votes
1answer
88 views

Total chromatic number and total clique number

Let $G=(V,E)$ be a finite, simple, unconnected graph. We define the total graph $T(G)$ of $G$ as follows: $V(T(G)) = (V\times\{0\}) \cup (E\times\{1\})$, $E(T(G)) = E_v \cup E_e \cup E_{v+e}$, where ...
0
votes
0answers
41 views

Generating tournaments inductively

This is a somewhat vague question, but I'm interested in ways to create a strong tournament from one or more smaller tournaments. Obviously, the disjoint union of two tournaments is a new tournament, ...
1
vote
0answers
71 views

Zero-one law in binomial random graph model $G(n,p)$

Consider the binomial random graph model $G(n,p)$ with $0<p<1$. We say that $G(n,p)$ satisfies the Zero-One law if for every first order property $Q$ one has $\lim\limits_{n \rightarrow \infty} ...
0
votes
0answers
43 views

Reconstructing a graph from set of sequences of edges

I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, find a "reasonable" reconstruction of the graph. There is an unknown number of ...
0
votes
0answers
17 views

is any closed form relation that can state the error probability of code versus its variable and check node degree distributions?

In Low Density parity check code design, when bit (or frame) error probability of code is the objective of the design, we need a closed form relation between error probably (or even an approximate or ...
0
votes
0answers
62 views

Binary operations on graphs

Are there "binary operations" on graphs like in (https://en.wikipedia.org/wiki/Graph_product), which make the set of all graphs ("under consideration") a (abelian) group or a (commutative) ring or a ...