**1**

vote

**0**answers

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

**3**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**3**answers

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

**3**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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