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

1
vote
0answers
28 views

Non-negative Polynomials from Polynomial Ideal?

Related to the thread Nonnegativity conditions for a polynomial in two variables? but on more than two variables. Suppose a probability vector $p$ belongs to a compact polytope where for each entry $...
24
votes
3answers
2k views

What is this subgroup of $\mathfrak S_{12}$?

On some occasion I was gifted a calendar. It displays a math quizz every day of the year. Not really exciting in general, but at least one of them let me raise a group-theoretic question. The quizz: ...
8
votes
1answer
589 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 ...
4
votes
0answers
88 views

A color interpolation lemma

I need the following "color interpolation lemma". Actually I know a way to prove it, but I'm not very satisfied with that proof. Lemma. Let $G=(V,E)$ be a (properly) colored graph with colors $1, \...
0
votes
1answer
58 views

Computing canonical forms from orbit partitions

Suppose we know the orbit partition of the vertices of a graph (due to the action of its automorphism group). Is it easy (as in "polynomial time") to generate a canonical form (aka "canonical labeling"...
0
votes
1answer
48 views

Count Functional digraph [on hold]

Given a set of nodes, how can I count the number of different functional digraph containing a specific number of connected components? With a restriction that no node can have an edge point to itself. ...
0
votes
0answers
24 views

On balanced bipartite graphs

Of the $2^{n^2}$ balanced bipartite graphs on $2n$ vertices how many of them have $i$ perfect matchings where $i\in\Bbb N\cup\{0\}$ and $0\leq i\leq n!$ holds?
28
votes
2answers
1k views

Should axiomatic set theory be translated into graph theory?

Recently I saw the abstract of a paper by Nash-Williams: ``Should axiomatic set theory be translated into graph theory?''. The abstract, taken from Mathscinet says the following: The author ...
3
votes
2answers
545 views

Bound on graph domination number when min degree is 7

I have a graph $G$ whose minimum vertex degree is $\delta=7$. I am seeking an upper bound on the domination number $\gamma(G)$ in terms of the number of vertices $n$ of $G$. I found a paper by Edwin ...
0
votes
1answer
63 views

On some examples of critical families

I'm reading the book on Injective choice functions by Holz, Podewski and Steffens, and I find it to be at the same time well written and quite difficult. It has almost no examples - and in quite a few ...
4
votes
1answer
548 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 \...
0
votes
1answer
36 views

Length of longest directed circuit in random tournament

Build a random tournament $T=(V,E)$ on $V=\{1,\ldots, n\}$ in the following fashion: for $i < j\in \{1,\ldots, n\}$ let the probability be $0.5$ whether $(i,j)\in E$ or $(j,i)\in E$ (in a ...
4
votes
0answers
102 views

Automorphisms of an infinite graph built from a finite motif

Suppose we have a lattice $L$ in $\mathbb{R}^n$ for which we choose some fundamental domain $D\subset \mathbb{R}^n$ homeomorphic to a closed ball. Translates of $D$ by distinct elements of $L$ ...
8
votes
3answers
577 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 ...
7
votes
3answers
199 views

When can the Cayley graph of the symmetries of an object have those symmetries?

Let $P$ be an object in $\mathbb{R}^n$ with symmetry group $G$. Let $C$ be the a Cayley graph of $G$. When can $C$ be embedded in $\mathbb{R}^m$ so that the embedded graph has the same symmetry ...
2
votes
1answer
132 views

Size of automorphism group of random regular graph

If I pick a random regular graph on $n$-vertices and degree $d$ from uniform distribution what is the probability that its automorphism group is of size at least $m$? -- I want to know what is the ...
2
votes
1answer
171 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$ ...
3
votes
0answers
64 views

Minimal algebraic degree of symmetric unit distance embedding of Heawood graph

I'm looking at embeddings of the Heawood graph in the plane as unit distance graph. Apparently the first such embedding was given by Gerbracht, 2009 and has algebraic (over the rationals) coordinates ...
0
votes
1answer
58 views

Counting and constructing some special planar graphs

We look for the property that a graph is both planar and has a trivial automorphism group. How many non-isomorphic $n$-vertex graphs have such property and is there an $O(n^\beta)$ (at least ...
0
votes
1answer
257 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
106 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} ...
4
votes
1answer
97 views

Connection between PageRank and Fiedler vector

This question is on graph clustering. In its simplest form, the eigenvector corresponding to the second smallest eigenvalue of the normalized Laplacian of a graph provides a relaxed solution to the ...
4
votes
1answer
191 views

Do right-profiles determine graphs up to isomorphism?

For graphs $G$ and $H$, let $h(G,H)$ denote the number of graph homomorphisms from $G$ to $H$. Fix some enumeration $G_1,G_2,\ldots$ of (isomorphism classes of) the set $\mathbf{D}$ of finite graphs, ...
1
vote
1answer
78 views

How to compute graph ideal or cut ideal of a graph?

Graph ideals are a special case of Stanley-Reisner ideal, explained in Combinatorial Commutative Algebra book by Sturmfels, and graph ideals here. Graph ideals are generated by the minimal paths while ...
4
votes
1answer
243 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' ...
7
votes
1answer
450 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 ≥ ...
1
vote
0answers
59 views

Non-orientable genus of union of graphs

It is known that the orientable genus of union of two (disjoint) graphs is the sum of their genus. So, it is natural to ask What can be said about the non-orientable genus of union of two (disjoint) ...
3
votes
1answer
81 views

Bounds for number of edges of a graph, given girth and number of vertices

In reading a paper, I came across an affirmation "a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges" In a previous question I asked in this site about it, I was reffered to a ...
1
vote
1answer
174 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 ...
2
votes
1answer
84 views

Existence of a Connectivity Polynomial for a simple graph?

I try to find a polynomial for an arbitrary simple graph $G$ that tells whether the graph is connected or not. A graph is st-connected if you can find a path between a vertex $s$ and a vertex $t$ -- ...
1
vote
1answer
116 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 ...
1
vote
1answer
338 views

Name for minimum size of a set of vertices S such that every other vertex has a neighbor in S

Given a (non-multi)graph $G$ let $N_G$ be the least number of nodes that must be colored (by a single color) such that every other node in $G$ shares an edge with at least one colored node. (I am only ...
2
votes
0answers
57 views

Induced matchings in a bipartite graph with every matching having the same number of edges

Suppose $n,k$ are positive integers such that $k\mid n$. Consider a bipartite graph $H=(A,B,E)$ such that $|A|=|B|=n$ and the edge set $E$ consists of the union of $m(H)$ induced matchings with every ...
7
votes
1answer
148 views

Does an expander remain an expander after removing few vertices and edges?

Consider a sequence of expander graphs ($G_n$); say $G_n$ has $n$ vertices. Remove $o(n)$ vertices (and the edges emanating from these vertices) and cut $o(n)$ edges. Call $G'_n$ the largest connected ...
1
vote
2answers
176 views

edge graph reconstruction conjecture : set vs multi set

Why is the edge reconstruction conjecture stated with the deck defined as the multi set of graphs formed by deleting one edge? Can someone give an example of two graphs such that the edge deleted ...
5
votes
1answer
323 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 ...
0
votes
1answer
53 views

Looking for source: Max num of edges of graph with given number of vertices and given girth

In a paper I am reading, the author states: "It is simple and well known that a graph of girth $g$ and $q$ vertices has at most $q^{1+(O(1)/g)}$ edges" He says that a proof can be found on Extremal ...
6
votes
1answer
150 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 ...
8
votes
1answer
148 views

How many edges can be added to two circles before the graph becomes Hamiltonian?

Start with two $n$-circles $(v_1\cdots v_n)$ and $(w_1\cdots w_n)$ of vertice sets $V$ and $W$, where $n\ge 5$. Add a number of vertex-disjoint edges between $V$ and $W$ (thus no chords) in a way ...
0
votes
2answers
123 views

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
76 views

Partitioning finite directed graphs into 3 “incoming-sparse” sets

Let $G=(V,E)$ be a directed graph. For $v\in V$ set $\text{In}(v)=\{x\in V: (x,v)\in E\}$. Is it possible to find a partition $P_1,P_2,P_3$ of $V$ such that for every $P_i$ and every vertex $v\in ...
0
votes
1answer
119 views

Does the shortest distance between two cities of a Traveling Salesman Problem always appear in the answer? [closed]

If I had a list of 4 or more cities, then does the path between the two closest cities always appear in the final shortest route of a TSP Solution? Bill
1
vote
0answers
78 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,...
6
votes
0answers
100 views

On the use of Weisfeiler-Leman refinement in Babai's GI proof

This question is for those familiar with the methods behind Babai's recent proof that graph isomorphism can be decided in quasipolynomial time. I am a newcomer to the GI problem, so I apologize if my ...
1
vote
2answers
218 views

Extended Hypercube Graph

Definition 1. The $n$-hypercube graph has vertices which are the elements of the set $\lbrace 0,1\rbrace^n$ of $n$-bit binary strings, and an edge is drawn between each pair of vertices representing a ...
3
votes
1answer
165 views

Alternative parallel paths

There are $n$ non-intersecting strings (with ends $x_1,\dots, x_n$ and $y_1,\dots, y_n$). An additional string intersects the first $n$ strings somehow. All the intersections are simple (vertices of ...
10
votes
1answer
287 views

Question on a paper by Benjamini/Kozma/Wormald about a “well known fact”

In "The mixing time of the giant component of a random graph" by the aforementioned authors, in the last proof on page 19 it says something along the lines of "It is well known and easy to verify ...
0
votes
0answers
24 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 ...
3
votes
1answer
77 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 ...
2
votes
0answers
81 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 ...