# Tagged Questions

**0**

votes

**0**answers

40 views

### asymptotic notation with graph colouring

This is my first ever post so I hope this is an appropriate question.
Basically I am looking at the paper here: http://homepages.math.uic.edu/~mubayi/papers/biclique.pdf
Namely theorem 5.
Now, feel ...

**10**

votes

**0**answers

315 views

### Is this graph polynomial known? Can it be efficiently computed?

I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...

**5**

votes

**0**answers

52 views

### Set system with prescribed intersection sizes

Questions: What is the asymptotic maximal size of a $4$-uniform (every set has 4 elements) set system $\mathcal{A}$ of subsets of $[n]$ such that, no two sets have size of their intersection $2$?
In ...

**6**

votes

**2**answers

178 views

### What is the number of noncrossing acyclic digraphs?

A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross ...

**5**

votes

**1**answer

116 views

### Graphs where each edge belongs to the same number of 1-factors

Let $G$ be a simple connected graph that has at least one 1-factor. We'll define:
$G$ has property A iff it is edge-transitive.
$G$ has property B iff each edge belongs to the same number of ...

**1**

vote

**1**answer

104 views

### Vertex transitive and edge transitive and line graph

How can we find the proof of the following statement:
An undirected graph is edge transitive if and only if its line graph is vertex transitive.

**23**

votes

**2**answers

474 views

### Removal of non-isomorphic edges results in the same graph

There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...

**0**

votes

**0**answers

37 views

### Complexity of graph isomorphism in $(P_4 \cup K_1,\overline{3K_2})$-free graphs

Related to this question where isomorphism preserving
transformation maps triangle-free graphs to $(P_4 \cup K_1,\overline{3K_2})$-free graphs.
What is the complexity of graph isomorphism in $(P_4 ...

**3**

votes

**1**answer

97 views

### Graph transformation related to graph isomorphism

Basically got graph transformation related to graph
isomorphism.
Define $G \to G'$. $V(G')=V(G) \cup E(G)=\{v_1\ldots v_n\} \cup \{e_1\ldots e_m\}$. Call $v_i$ vertices $v'$ and $e_i$ vertices $e'$.
...

**7**

votes

**0**answers

87 views

### Algorithms for computing the Resilience of Graphs

The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...

**0**

votes

**0**answers

92 views

### Reduction from permanent to $(0,1)$-permanent and implication of $P \ne NP$

Valiant
shows reduction from counting the solutions of CNF formula $F$,$\#SAT(F)$
to computing permanent where $ Perm(A)= 4^{t(F)}\cdot \#SAT(F)$
for certain efficiently computable $t(F)$ and matrix ...

**6**

votes

**2**answers

163 views

### Find multiple non-adjacent paths in a graph

Consider a non-directed graph. I want to find as many non-adjacent paths as possible from a source $s$ to a destination $t$. Two paths $P_1$ and $P_2$ are said to be non-adjacent to each other if none ...

**4**

votes

**1**answer

111 views

### Product of geodesic distances

I'm working on trying to show this, but can't seem to get started. No guarantees that it is true, but other conditions on the adjacency matrix that make it true or a counter example are helpful. ...

**0**

votes

**4**answers

108 views

### about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...

**2**

votes

**1**answer

149 views

### Clique problem for regular graphs

I am looking for NP complete results for cliques in regular graphs. For example is the general problem of determining if a regular graph on n vertices has an n/2 clique NP-complete? (obviously the ...

**1**

vote

**0**answers

68 views

### Empty node in cactus construction

Is there a necessary condition for not having empty node in the construction of the cactus of the minimum cuts of a graph?
In particular is there a necessary condition for not having empty k-junction ...

**0**

votes

**1**answer

142 views

### Kneser graphs eigenvalues

Basically, I want to prove that, in the Kneser graph (wikipedia has a good definition),$K_{n, m}$, if $n_{-}(A(G)) $ and $n_{+}(A(G))$ denote the number of negative and positive eigenvalues of A(G) ...

**6**

votes

**2**answers

197 views

### Conjecture: for perfect graphs the fractional chromatic index rounded up equals the chromatic index

Let $\chi'_f(G)$ be the fractional chromatic index.
Based on limited experiments (up to 8 vertices and few larger graphs),
I suspect:
Conjecture For perfect graphs $\lceil \chi'_f(G) \rceil = ...

**2**

votes

**1**answer

88 views

### Estimate for the travelling salesman problem for balls inside a grid

This question is probably easy but I only have "tedious case checking" proof strategy in sight, and I'm sure there should be a reference lying around...
The question concerns the TSP problem (with ...

**4**

votes

**2**answers

184 views

### Roots of matching polynomial of graph

At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial:
If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...

**1**

vote

**0**answers

49 views

### Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).
Are there graph problems that can be solved in
...

**1**

vote

**0**answers

48 views

### Asymptotic results in unbalanced left $d$-regular expander graphs

Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$.
Call a graph $G = (U, ...

**6**

votes

**0**answers

123 views

### The Universal Labeling of graph

The universal labeling of a graph $G$ is a labeling of the edge set in $G$ such that in every orientation $\ell$ of $G$ for every two adjacent vertices $v$ and $u$, the sum of incoming edges of $v$ ...

**8**

votes

**1**answer

158 views

### Spectral lower bounds on the diameter of a graph

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:
$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$
This bound is very elegant but ...

**5**

votes

**1**answer

145 views

### Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.
The famous Nash-Williams conjecture claims ...

**4**

votes

**2**answers

219 views

### Equality-preserving embeddings of finite trees

For finite trees $T_{1}$ and $T_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be ...

**8**

votes

**5**answers

977 views

### Are all almost regular graphs obvious?

Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively.
A graph is almost regular if $\Delta-\delta=1$.
Now, here is a simple way to generate ...

**5**

votes

**0**answers

93 views

### Monotone embedding of complete binary tree in hypercube

Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...

**5**

votes

**0**answers

144 views

### Are the roots of chromatic polynomials plus a fixed constant dense in $\mathbb{C}$?

Alan Sokal proved that chromatic roots are dense in the whole complex plane. I.e., if $P(G;z)$ denotes the chromatic polynomial of a finite simple graph $G$ evaluated at $z \in \mathbb{C}$, then ...

**2**

votes

**3**answers

153 views

### Examples of graph properties characterized by forbidden (not necessarily induced) subgraphs

A graph property is hereditary if it is closed under taking induced subgraphs (equivalently, if it is closed under removing vertices). A graph property is monotone if it is closed under taking ...

**1**

vote

**0**answers

62 views

### labeling vertices in a graph to minimize distance between adjacent vertices

We have a regular graph $G$ of degree $m$ on $n$ vertices and we label each of its vertices with the number $1$ through $n$. What can we say about the maximum difference between the numbers of two ...

**6**

votes

**1**answer

348 views

### Paths in groups

Given a finite group $G$, write $K(G)$ for the complete digraph on the elements of $G$. Label the edge from $g$ to $h$ by element $g^{-1}h$.
Question: For what groups does there exist a Hamiltonian ...

**1**

vote

**1**answer

121 views

### Sequences that represent different drawing of chords?

In combinatorics there are there are special kind of sequences, in which their terms represent the number of different ways that we can draw chords with some properties.
Actually my question is ...

**16**

votes

**0**answers

146 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...

**1**

vote

**0**answers

109 views

### Relationship betwen eigenvectors

Suppose that we have two matrices A and B. Matrix B is taken from A with one row and one column deleted. On the other hand A is n*n matrix and B is (n-1)*(n-1) matrix and is created by deleting last ...

**10**

votes

**1**answer

453 views

### Where can I find Gonthier's Coq code proving the four color theorem?

In a 2008 article in the Notices, Georges Gonthier announced a computer-checked proof of the four color theorem using Coq:
Gonthier, Georges. Formal proof—the four-color theorem.
Notices Amer. ...

**3**

votes

**1**answer

113 views

### Cayley graph which is isomorphic to the line graph of a complete graph

From the literature, we know that the line graph of a complete graph $L(K_{q})$ is a Cayley graph if and only if $q \equiv 3$( mod 4) is a prime power. Now, if $q \equiv 3$( mod 4) is a prime power, ...

**3**

votes

**0**answers

55 views

### Maximal $k$-chordal subgraph

Recall that a graph is called $k$-chordal if any cycle $C$ of length $> k$ contains a chord, i.e. an edge joining to non-consecutive vertices in $C$. Let $f(n, k)$ be the minimal number of edges ...

**4**

votes

**1**answer

180 views

### Extremal graph theory for directed graphs

In extremal graph theory, there are results such as
$$t(C_4,G)\geq t(K_2,G)^4,$$
where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and ...

**7**

votes

**4**answers

304 views

### Extremal examples for a folklore lemma on subgraphs of large minimum degree

It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by ...

**2**

votes

**2**answers

154 views

### Degree Sequence Problem on $k$-Partite Graphs

The general Degree Sequence Problem asks for a simple undirected graph (that is a graph without self-loops and with no more than one edge between any pair of nodes) for which it holds that the degrees ...

**3**

votes

**2**answers

171 views

### Definition of the Moebius Ladder Graph

I found two different definitions of the Moebius Ladder Graph, whose essential difference is, whether the smallest one shall be $K_4$ or $K_{3,3}$.
according to Wikipedia ...

**2**

votes

**2**answers

127 views

### Which graphs generate a matroidal independence complex?

The independence complex $I(G)$ of a graph $G=(V,E)$ has as point set the vertex set $V$ and as simplices the independent sets of $G$.
Now, if $G$ is a well-covered graph (where all maximal ...

**0**

votes

**0**answers

41 views

### Almost symmetric route in digraphs

Let $D=(V,E)$ be a digraph. A route of length $k$ in $D$ is a pair $L=(S,\sigma)$, where $S=(s_1,s_2,\dots,s_{k+1})$ is a sequence of $k+1$ elements of $V$, and ...

**14**

votes

**1**answer

1k views

### What have simplicial complexes ever done for graph theory?

(I am asking in a somewhat tongue-in-cheek fashion, of course, but nevertheless...)
Are there examples of results in "classical" [*] graph theory that have
been achieved by using simplicial ...

**1**

vote

**1**answer

111 views

### The edge chromatic number and pefectness of inflation of cubic graph

The inflation of graph $G$ is a graph $I(G)$
which is obtained by replacing each vertex $x$ by a complete graph
$K_{\deg(x)}$ and joining each edge to a different vertex of $K_{\deg(x)}$.
Let $G$ ...

**4**

votes

**1**answer

182 views

### Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge.
Note that the number of paths between two endpoints of a $k$-chain is $2^k.$
Question: Let ...

**1**

vote

**0**answers

121 views

### Knight's metric: ellipse and parabola

Knight's metric is a metric on $\mathbb{Z}^2$ as the minimum number of moves a chess knight would take to travel from $x$ to $y\in\mathbb{Z}^2$. What does a parabola (or an ellipse) became with this ...

**9**

votes

**3**answers

727 views

### Could a perfect squared square be split into two perfect squared squares?

This is a geometric puzzle though it might conceivably
also define a special class of Pythagorean triples.
A perfect squared square PSS is a square (as a plane figure)
partitioned into smaller ...

**1**

vote

**1**answer

118 views

### Max order for which connected Cayley Graphs are known to be Hamiltonian

There is a well-known conjecture that all connected Cayley graphs are Hamiltonian.
For how large a value of n has the conjecture been verified (i.e., for all groups whose order is at most n)?