# Tagged Questions

**0**

votes

**0**answers

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

**2**

votes

**0**answers

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

**1**

vote

**1**answer

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

**8**

votes

**1**answer

582 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**0**

votes

**0**answers

84 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

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

**1**

vote

**1**answer

104 views

### Counting bounded genus non-isomorphic graphs

What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$?
I am most interested in $d\leq3$ and $g=0$.

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

**1**answer

273 views

### Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$).
The cost to send $x$ unit of flow through edge $e_i$ is defined ...

**8**

votes

**3**answers

520 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

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

**4**

votes

**1**answer

510 views

### inequality with exponents

We are given a graph $G$, each vertex $v$ has an assigned value $\gamma_v\in [0,1]$, and it happens that for every $v$ we have $\gamma_v+\sum_{u\in \delta(v)} \gamma_u = 1$. Assume that $\sum_v \...

**-5**

votes

**0**answers

53 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

**1**answer

73 views

### Choosing directed subgraph in a triangulation

Consider triangulation $T.$
Is it always possible to choose such a subgraph $H$ of $T$ that has a common edge with every face of $T$ and can be directed in such way that indegrees of all vertices of ...

**-1**

votes

**0**answers

19 views

### decomposition of graphs into edge-disjoint subgraphs [closed]

I am reading a paper "Decomposition of complete bipartite graphs into paths and cycles",I would like to know whether it has any applications in other fields(other than math)such as networks or ... ?
...

**0**

votes

**0**answers

22 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

269 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

**1**answer

154 views

### Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...

**10**

votes

**7**answers

1k views

### Where on the internet I can find database of graphs?

I am studying graph algorithms.
I need database of graphs on which I can test my algorithms.
Where can I find reliable database of graphs of all kinds?
Thanks!

**3**

votes

**3**answers

288 views

### Hashimoto Matrix (Non-backtracking operator) and the Graph Laplacian

The question is: how can we recover the graph Laplacian or its spectrum from the Hashimoto Matrix (also commonly called the Non-backtracking operator)?
To make the question as self-contained as ...

**-2**

votes

**0**answers

20 views

### General Form of 2D Lorentzian Confirmation [closed]

Is the general form of a 2D Cauchy Peak, if A is the amplitude:
$$\frac{A}{1+\frac{(x-x_0)^2}{\gamma_x^2}+\frac{(y-y_0)^2}{\gamma_y^2}}$$
or $$\frac{A}{(1+\frac{(x-x_0)^2}{\gamma_x^2})*(\frac{(y-y_0)^...

**2**

votes

**0**answers

40 views

### A graph partition problem related to the degree of the vertices

Let $G=(V,E)$ be a simple graph. For disjoint $A,B\subset V$, $e(A,B)$ is
the number of edges between $A$ and $B$.
Let $max\{e(A,B):\{A,B\}\ \text{is a partition of}\ V\}=L(G)$. Then if $\{A,B\}$ is ...

**0**

votes

**1**answer

255 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...

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

**5**

votes

**1**answer

290 views

### Paley graphs over $p^{2}$ vertices

I have proved that every Paley graph $P(p^{2})$ over $p^{2}$ vertices, where $p\geq 5$ is a prime number has a cospectral mate, i.e. for every prime number $p\geq 5$ there exists a graph $\Gamma_{p}$ ...

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

108 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$,...

**1**

vote

**1**answer

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

**0**

votes

**0**answers

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

**10**

votes

**2**answers

644 views

### Expected number of connected components in a random graph

For a random graph G(n,p) what is the expected number of connected components? What is the probability distribution of this value?
I'm specially interested in what happens for small values of p, ...

**1**

vote

**0**answers

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

**3**

votes

**1**answer

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

**4**

votes

**1**answer

226 views

### minimal polynomial for a graph

I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...

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

**7**

votes

**1**answer

443 views

### How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.
A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...

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

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

**2**answers

794 views

### Find all faces in a graph from list of edges

I have the information from a undirected graph stored in a 2D array. The array stores all of the edges between nodes, e.g. graph[3] might be equal to [1,8,30] and represents the fact that node 3 ...

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

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

**1**

vote

**1**answer

157 views

### Product and coproduct for bipartite graphs

Consider the category $BiGraph$ of bipartite graphs (vertices are named "places" and "transitions" like in Petri nets) and continous maps. A subgraph is named open iff it is place-bordered, and a map ...

**1**

vote

**1**answer

103 views

### Assigning random orientation to an edge in a regular graph

Given a simple regular graph of degree $d$ on $n$ vertices.
Assume an ordering of vertices and assume all orientations of edges is from $i$ to $j$ if edges $ij$ exists and $i<j$. Pick $m$ random ...

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

**5**

votes

**1**answer

267 views

### Graph spectra and topology

This is a somewhat vague question, but I'm wondering if there has been any research into connections between the spectrum of a graph and some notion of the "topology" of that graph.
To give an ...

**6**

votes

**1**answer

134 views

### Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...

**0**

votes

**0**answers

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

**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?