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

learn more… | top users | synonyms

2
votes
1answer
145 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 ...
6
votes
1answer
339 views

How does the distribution of Erdős number evolve over time ? How to build a model to fit the real data ?

Let $E(n,t)$ be the number of mathematicians with finite positive Erdős number $n$ at time $t$. As old mathematicians leave, and new mathematicians come, how does $E(n,t)$ change over time ? We can ...
2
votes
2answers
281 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 ...
-1
votes
0answers
36 views

find all path segments in an undirected graph [on hold]

I have an undirected graph, like the following: . C . / \ . B F . / / \ . A D E The edges are: ...
2
votes
1answer
164 views

Cospectrality and dimension of graphs

Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas. In the following all graphs are simple and connected. Let $G$ be graph with vertex set ...
-1
votes
0answers
63 views

I need help in understanding O(nlogn) question [on hold]

I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well. On to my question. Before I do, this is a class question that has been asked, ...
4
votes
0answers
58 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
2answers
98 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 ...
40
votes
4answers
5k views

Do there exist chess positions that require exponentially many moves to reach?

By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an ...
-4
votes
1answer
45 views

Survey on Hypergraph Theory [closed]

I want to learn about hypergraphs.Can anyone help me with some links, articles and surveys. Thanks
2
votes
0answers
58 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
0answers
50 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 ...
19
votes
1answer
602 views

Monomer-Dimer tatami tilings need better relationships with other math. Summary of results.

A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the \emph{tatami} condition if no four tiles meet at any point. (or you can think of it as the removal of a ...
5
votes
1answer
278 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 ...
5
votes
0answers
134 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 ...
5
votes
1answer
315 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 ...
0
votes
1answer
82 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 ...
1
vote
0answers
68 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
0answers
32 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 ...
0
votes
1answer
72 views

N random walkers that hit node v in a graph

Consider a finite, undirected graph G, with uniform edge weights. Assume that there are n number of random walkers that will start at different nodes (lets say n=3, hence the random walkers will start ...
8
votes
1answer
359 views

Bicycles and spanning trees of graphs

A spanning tree in a graph is a connected spanning subgraph with no cycles; it is well known that the number of spanning trees can be found by taking the determinant of a certain matrix related to the ...
2
votes
1answer
185 views

Coloring vertices in a cubic lattice graph and counting edges between vertices of identical and vertices of distinct coloration

Take an $A \times B \times C$ cubic lattice graph $G$, and paint $k_1$ vertices with color $c_1$ & $k_2$ vertices with color $c_2$, where $(k_1 + k_2)$ is equal to the total vertex count. Let ...
0
votes
1answer
115 views

Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$). The cost to send $x$ unit of flow through edge $e_i$ is defined ...
9
votes
1answer
310 views

Coherence between different ranking methods of a graph's vertices

Given a (connected) graph $G$ it is natural to want to rank its vertices, with the more "central" vertices ranked higher. Two natural ways of doing it are: By the degrees. By the entries in a ...
1
vote
0answers
49 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 ...
5
votes
1answer
403 views

Edge Covering Shortest path

I have a graph of Points G(V,E) and I want to find the shortest path covering all the edge, I want the minimum number of edge repetitions . Which is the best way to reduce this problem to well know ...
1
vote
1answer
85 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 ...
3
votes
0answers
57 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 ...
4
votes
2answers
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 ...
2
votes
1answer
61 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
0answers
73 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
2answers
162 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
0answers
66 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 ...
1
vote
0answers
53 views

Programmatically recognizing symmetries of a polyhedron

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: ...
0
votes
1answer
133 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 ...
1
vote
0answers
87 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 ...
8
votes
1answer
343 views

What is the correct statement of this Erdös-Gallai-Tuza problem generalizing Turan's triangle theorem?

In Zsolt Tuza's Unsolved combinatorial problems I, Problem 46 is the following conjecture: Let $G$ be a graph on $n$ vertices. Let $\alpha_1$ be the maximum number of edges of $G$ such that every ...
2
votes
1answer
74 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 ...
4
votes
1answer
209 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 ≥ ...
7
votes
1answer
184 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 ...
25
votes
3answers
587 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 ...
1
vote
1answer
96 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 ...
0
votes
2answers
120 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
1answer
83 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 ...
4
votes
0answers
87 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 ...
10
votes
1answer
586 views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time. ...
3
votes
1answer
134 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 ...
6
votes
1answer
166 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 ...
8
votes
1answer
167 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
2answers
239 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) = ...