**3**

votes

**0**answers

121 views

### What do we know about isospectral Cayley graphs?

Let $\Gamma_1=\Gamma_1(G_1,S_1)$ (respectively $\Gamma_2=\Gamma_2(G_2,S_2)$) be a Cayley graph for the group $G_1$ and the finite generating set $S_1$ (respectively $G_2$ and the finite generating set ...

**0**

votes

**0**answers

49 views

### Induced subgraphs on a Laminar family of vertices with constant diameter

$X$ is a family of subsets of $V$. $X$ is called a Laminar family on $V$ if for all $A,B\in X$, either $A\cap B=\emptyset$, $A\subset B$ or $B\subset A$.
Let $X$ be a family of subsets of $V$. A ...

**0**

votes

**1**answer

66 views

### Paper on unit disk graphs

I was wondering if anybody knows of a 'link' to the paper by Marathe 1995 et al on analysis of the greedy algorithm for finding a Max independent set in Unit Disk Graphs?

**2**

votes

**0**answers

28 views

### “drift” of a random graph $G(n,p)$ with $p=\alpha\ln{n}/n$

Suppose $G\sim G(n,p)$ with $p=\alpha\ln{n}/n$ for some large constant $\alpha$. I wish to show a certain "drift" property of $G$, which can roughly be phrased as follows: if $u$ is "not that far" ...

**1**

vote

**1**answer

54 views

### Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...

**2**

votes

**4**answers

263 views

### Algorithm to find the “optimal” path in a given graph

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...

**2**

votes

**1**answer

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

**2**

votes

**3**answers

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

**0**

votes

**1**answer

170 views

### Coin graph is 4-colorable

How can we prove that a coin graph is 4-colorable???Also, can we find any example of an non-3-colorable coin graph.

**3**

votes

**1**answer

89 views

### Independent Sets in random geometric graphs

I was wondering if a lot is known about independent sets in Random Geometric graphs? Most google searches don't bring up much. In addition I'm interested in any algorithms used for finding independent ...

**1**

vote

**2**answers

128 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

**0**answers

44 views

### Weighted graph similarity

I have the following problem. Consider an undirected biconnected graph with $n$ vertices and $m$ edges ($n \leq m \leq n(n-1)/2$). The $m$ edges of the graph are then "populated" by integer weights ...

**2**

votes

**1**answer

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

**4**

votes

**0**answers

69 views

### Subgraphs of planar trivalent graphs

Let's think about planar trivalent graphs. (Or you can dualize and think about triangulations if you prefer.) It's easy to come up with a list of 'planar trivalent graphs with boundary' such that at ...

**1**

vote

**2**answers

113 views

### Minimum number of unlabeled planar graphs

Does anybody know if there is any research on a lower bound on the number of (non-isomorphic) unlabeled planar graphs with maximum node degree $d$?
Alternatively, a lower bound on the number of all ...

**-4**

votes

**1**answer

58 views

### Survey on Hypergraph Theory [closed]

I want to learn about hypergraphs.Can anyone help me with some links, articles and surveys.
Thanks

**3**

votes

**0**answers

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

**2**

votes

**0**answers

56 views

### Problems Solvable/Decidable by Counting Shortest Paths in Graphs

This questions is based on a dispute, whether it would be possible to calculate 'nice' routes in Manhattan, if the road network is assumed to be a rectangular grid and, that 'nice' means that there is ...

**5**

votes

**1**answer

300 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

88 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

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

**1**

vote

**0**answers

73 views

### Disks in Flat Embeddings of Graphs in $\mathbb{R}^3$

Robertson, Seymour and Thomas proved that any linkless graph $G$ has a flat embedding in $\mathbb{R}^3$ (see for example A survey of linkless embeddings). An embedding of $G$ is flat if for any cycle ...

**2**

votes

**1**answer

63 views

### Hamiltonicity of random graphs with high girth

We say that $G\sim G_{n,f}$ (for $f=f(n)$) if $G$ is chosen uniformly at random from all graphs on $n$ vertices with girth $g(G)\ge f(n)$. Is there any threshold function $F(n)$ such that when $f\ll ...

**1**

vote

**0**answers

65 views

### Possible ways to create a graph representation from a distance matrix (through approximation)

Forgive me, Im not math professional, but a computer scientist at the beginning of my base research from my thesis, so bare with me if I miss something blatantly obvious.
I have a Euclidean distance ...

**3**

votes

**0**answers

62 views

### Different definitions of linkless graphs

Robertson, Seymour and Thomas defined linkless embeddings of graphs as follows:
An embedding of $G$ is linkless if every pair of disjoint circuits of $G$ have zero linking number (see here). However ...

**1**

vote

**1**answer

94 views

### Difference between straight and piecewise linear and continuous embeddings of graphs / complexes in d-dimensional space?

Here is my main question: what is the difference between "straight" and "piecewise linear" and "continuous" embeddings of graphs/complexes in d-dimensional space?
Moreover I would like to know if any ...

**2**

votes

**2**answers

353 views

### Categories with binary relations as objects

For the category of functions, pairs of functions making commutative diagrams are the canonical morphisms $\alpha:f\rightarrow g$. For binary relations there is an alternative, to consider the ...

**2**

votes

**1**answer

66 views

### Coloring graph such that the coloring classes are not maximal independent sets

Let $G$ be a (finite or infinite) simple graph. We let $\mathrm{Ind}(G)$ be the collection of independent sets. For any cardinal $\kappa$ and coloring map $\chi: G\to \kappa$ we have ...

**2**

votes

**0**answers

79 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

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

**0**

votes

**0**answers

55 views

### Programmatically recognizing symmetries of a polyhedron [closed]

I asked this question on MSE a month ago, but nobody was able to answer it, so I guess the question is more difficult than I initially thought: ...

**4**

votes

**2**answers

144 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

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

**0**

votes

**0**answers

67 views

### A certain Acyclic Partition of a digraph

Has the following object been defined in the literature? What is it called? And what literature studies it? Are there other characterizations of this? What properties are known?
Let $G$ be a directed ...

**2**

votes

**1**answer

77 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

200 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

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

**2**

votes

**1**answer

92 views

### What is the minimal girth of a cayley graph for Alt(n) in which the girth relator is not a proper power?

First, a definition: a girth relator for a Cayley graph is a word that you get by reading the edge labels along a shortest loop. The girth relator is not usually unique, though it is often unique up ...

**5**

votes

**1**answer

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

**3**

votes

**1**answer

138 views

### Contracting a planar graph to a (multiply-edged)-tree

Given a planar graph (no loops, no multiple edge), is it always possible to perform edge contractions* in order to obtain a graph $T$ which has no loops, but if one forgets the multiplicity of its ...

**8**

votes

**1**answer

175 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

176 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

249 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

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

**5**

votes

**0**answers

82 views

### Mapping graphs to ordinals

Robertson-Seymour theorem implies that graph minor relation is a well-quasi-ordering, which means (among other things) that this relation can be extended to a well-order, and other result says that ...

**2**

votes

**0**answers

49 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

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

**2**

votes

**0**answers

64 views

### Properties of a smallest tournament with domination number $k$

For some tournament $T$, let $\gamma(T)$ denote the cardinality of a smallest dominating set of $T$.
Denote by $f(k)$ the minimum number of vertices of a tournament $T$ having $\gamma(T) = k$.
From ...

**1**

vote

**1**answer

67 views

### Two definitions of genus for circle graphs

In the (very nice) article of Goldstein and Turner untitled Applications of Topological Graph Theory to Group Theory, the following definitions can be found:
Definitions: A circle graph is a pair ...

**6**

votes

**2**answers

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