# Tagged Questions

**2**

votes

**1**answer

43 views

### Existence of neighborhood inclusion for 4-chordal graphs

Let $N(v)$ be the (open) neighbourhood set of a vertex $v$, and let $N[v]$ be the closed neighbourhood set of $v$.
A graph $G$ is called 4-chordal if $G$ has no induced cycle with five or more ...

**1**

vote

**3**answers

177 views

### a colouring / matching problem

While trying to find a bijection which preserves various combinatorial statistics, I was led to the problem below. Very much to my surprise, a closely related question, Coloring summands of given ...

**1**

vote

**2**answers

118 views

### Non-DS circulant graphs

Let $p$ be a prime number greater than or equal to 11. Are there any cospectral non-isomorphic graphs with circulant graphs on $p$ vertices.
Which circulant graphs over prime number of vertices ...

**2**

votes

**1**answer

177 views

### On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections

Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements.
We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we ...

**2**

votes

**0**answers

62 views

### More 3-connected cubic graphs with all 2-factors of same cycle type?

The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...

**5**

votes

**1**answer

290 views

### Are there number-theoretic graphs that are far from being isomorphic

I say that two graphs $G_1=(V_1,E_1)$, $G_2 = (V_2,E_2)$
with the same number of vertices, edges,
are $\epsilon$-far from being isomorphic, if for any bijection between $V_1$ and $V_2$, the fraction ...

**0**

votes

**1**answer

84 views

### Comparing ideals in posets

Consider a partially ordered set $P$, and two upper sets $U_1$, $U_2$ in this poset.
What are some natural ways to measure how equal these two upper sets are?
This question arise naturally in the ...

**5**

votes

**0**answers

137 views

### (Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples

Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...

**2**

votes

**0**answers

74 views

### second smallest eigenvalue Laplacian - submodular set function

Let $G$ be a connected unweighted undirected graph. In addition, let $\lambda_2(L(G))$ be the second smallest eigenvalue of the Laplacian matrix of graph $G$. Is $\lambda_2(L(G))$ a submodular set ...

**1**

vote

**2**answers

163 views

### Cubic Cayley (undirected) graphs

The generators of a cubic Cayley graph always include at least one involution, since 3 is odd. There are then two possibilties for the other two generators: either (A) they are also (distinct) ...

**4**

votes

**2**answers

130 views

### Minimum number of transitive paths in tournament

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if ...

**1**

vote

**0**answers

92 views

### Kempe chain color swaps in a partially colored map

Crossposted from math.stackexchange.com:
http://math.stackexchange.com/questions/904932/kempe-chain-color-swaps-in-a-partially-colored-map
Question: In this partially Tait's colored map, using ...

**2**

votes

**1**answer

75 views

### When does a hypergraph represent maximal independent sets?

Let $G = (V,E)$ be a simple graph. Then, we can view the set of maximal independent sets (or the set of maximal cliques) as a hypergraph $H = (V, E')$. This is quite a useful device when connecting ...

**7**

votes

**1**answer

189 views

### A conjecture about strongly regular graphs

Let $G \neq K_{v}$ be a $(v,k,\lambda,\mu)$ strongly regular graph. After perusing through Brouwer's tables of parameters I have formed the conjecture $$\lambda-\mu \leq \frac{k}{2}.$$
So far I have ...

**0**

votes

**2**answers

124 views

### Terminology for beads/necklace/bracelet problem [closed]

I'm new to mathoverflow but hopefully anyone here can point me in the right direction.
The problem is as follows, imagine you have 4 beads, lets give them numbers 1,2,3,4. Now I want the unique ...

**4**

votes

**0**answers

88 views

### Full-rank factorization of the graph Laplacian

Is there a combinatorially meaningful full-rank factorization of the Laplacian matrix of a graph?
The usual factorization $L=BB^{T}$, where $B$ is an oriented incidence matrix, is full-rank if and ...

**8**

votes

**1**answer

170 views

### Looking for history on a theorem of clique intersections

I have a short paper I'm working on where I prove:
Theorem: Every graph on (2t-1) vertices with no (t+1)-clique has a vertex that is contained in every t-clique.
By "t-clique", I mean a complete ...

**5**

votes

**1**answer

168 views

### Duration and critical groups order in sandpile models and chip firing games

The famous chip firing game (which is closely related to sandpile models) goes like this:
Place chips at the vertices of a graph. REPEATEDLY: If a vertex $v$ of
degree $d_{v}$ has at least ...

**5**

votes

**2**answers

243 views

### Matching number and chromatic number

If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$).
For odd integers $n$ we have $n=\chi(K_n) = ...

**0**

votes

**1**answer

43 views

### average number of cycles and closed walks length k in incomplete directed graph

I asked this question before, but formulation was poor. I've deleted previous question and reformulate it again.
Let graph $G=(N,p)$ is finite simple incomplete directed graph of size $N$ (multiple ...

**2**

votes

**0**answers

47 views

### When polynomial GI implies polynomial (edge) colored GI?

(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).
There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge ...

**2**

votes

**0**answers

47 views

### Looking for similar centrality measurement on graph

I'm working on a graph problem somehow related to centrality measurement. Given an undirected, unweighted tree $T$ and a vertex $v$, let $D_i(v)$ be the set of vertices in $T$ that are i hops from ...

**6**

votes

**2**answers

202 views

### Cubic graphs whose 2-factors all have the same cycle type

Let $G$ be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is ...

**0**

votes

**0**answers

71 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

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

**0**

votes

**0**answers

57 views

### How many edges are in the kth-iterated common neighborhood knight's graph?

For terminology see https://www.academia.edu/2180382/The_Common_Neighborhood_Graph_and_Its_Energy)
It has been known for quite some time by players that a vertex whose corresponding square is in the ...

**6**

votes

**0**answers

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

**7**

votes

**2**answers

264 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

130 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

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

**24**

votes

**3**answers

589 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

41 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

104 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

122 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

97 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

173 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

114 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

111 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

154 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

72 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

154 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

198 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

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

**5**

votes

**2**answers

202 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

51 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

52 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

132 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

167 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

155 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

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