# Tagged Questions

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

8 views

### Hypergraph clustering conductance Formula

Consider the Hypergraph $H=(V,E)$, with $V$ being the vertices and $E$ being the hyperedges. What is the formula of conductance $\Phi(S)$ for hypergraphs, with $S$ being a set of vertices (cluster ...
35 views

### How to flip a graph over the x-axis but retain the original equation [on hold]

I know this question seems really very basic for this forum, but after about an hour of trying to work it out for myself, I decided to look here for help. The premise I'm trying to create the graph ...
86 views

### Counting tournaments with ties

An improper tournament, or tournament with ties, is a graph in which every pair of nodes is connected by a single uniquely directed edge or by a single undirected edge. There are 1, 2, and 7 improper ...
75 views

### Regular tournaments

Let $T=(V,E)$ be a tournament. We call it regular if all vertices have the same out-degree. It is not hard to see that there are no regular tournaments on an even number of points. Let $n>0$ be an ...
54 views

133 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 ...
65 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 ...
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 ...
203 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 ...
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 ...
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 ...
79 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 ...
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) ...
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 ...
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$ -- ...
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 ...
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 ...
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 ...
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 ...
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
101 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 ...
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 ...
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,...
83 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 ...
81 views

### Is there currently a known way to construct an injective mapping that transforms finite graphs into discrete geometric objects? [closed]

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.
25 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 ...
213 views