# Tagged Questions

**0**

votes

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**3**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**3**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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