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
3 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,...
1
vote
0answers
34 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
27 views

Simple Arrangements of Chords Have Hamiltonian Circuits?

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
29 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
189 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
530 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
62 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
345 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 ...
-5
votes
0answers
54 views

How many non-isomorphic Fano planes exist? [closed]

How many non-isomorphic Fano planes exist? 1 down vote favorite 1 The Fano plane is the finite projective plane of order 2, having the smallest possible number of points and lines, 7 each, with 3 ...
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
58 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
61 views

Triange-free graph and its complement has Lovasz 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 ...