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
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
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
1answer
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
3answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
2answers
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
1answer
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
7answers
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
3answers
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
0answers
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
0answers
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
1answer
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
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 (...
5
votes
1answer
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
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
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
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 ...
0
votes
0answers
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
2answers
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
0answers
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
1answer
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
1answer
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
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 ...
7
votes
1answer
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
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
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
2answers
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
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 (...
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, ...
1
vote
1answer
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
1answer
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
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 ...
5
votes
1answer
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
1answer
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
0answers
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
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?