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

0
votes
2answers
101 views

Terminology for beads/necklace/bracelet problem [on hold]

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
67 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 ...
3
votes
0answers
69 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
1answer
124 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
1answer
147 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 ...
-4
votes
0answers
38 views

graph and tree problems helps [closed]

Let G = (V,E) be a graph and let H1 = (V1,E1) and H2 = (V2,E2) be two connected subgraphs of G that have at least one node in common. Prove that the graph H = H1∪H2 = (V1∪V2,E1∪E2) is connected. ...
6
votes
1answer
148 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
2answers
222 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
1answer
40 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
0answers
69 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 ...
1
vote
0answers
45 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
0answers
43 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
0answers
55 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
1answer
59 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 ...
5
votes
2answers
173 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 ...
6
votes
1answer
134 views

Smallest Connected Graph for Given Degree Sequence

For a given integer sequence $(d_1, d_2,...,d_n)$, a natural question is if such a sequence is graphical, i.e. is a degree sequence of some graph. According to Erdős–Gallai theorem, A sequence of ...
2
votes
0answers
109 views

NP-hard proof of optimization version of exact cover [closed]

Exact cover is NPC. http://en.wikipedia.org/wiki/Exact_cover#Equivalent_problems Given a collection $\mathcal{S}$ of subsets of a set $X$, an exact cover is a >>subcollection $\mathcal{S}^*$ ...
0
votes
1answer
41 views

Resource on characterizations or properties of traceable graphs

I am looking for some resources that provide information on traceable graphs(paths containing a hamiltonian path). I have found a lot of information on hamiltonian graphs, but none on traceable ...
0
votes
0answers
65 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 ...
6
votes
1answer
53 views

Is a connected graph uniquely determined by its weighted 2-step graph?

This is an extension of a previous question: Is a graph uniquely determined by its weighted 2-step graph?. In that question I asked about arbitrary graphs; in this question I restrict to connected ...
11
votes
0answers
365 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 ...
6
votes
0answers
66 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 ...
1
vote
1answer
86 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 ...
7
votes
2answers
244 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
1answer
125 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 ...
2
votes
0answers
158 views

Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate polynomial which counts the number of colorings of $G$ with $x$ colors for natural $x$. Graph is not $k$ colorable iff $P(G,k)=0$. The ...
1
vote
1answer
114 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
2answers
505 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 ...
10
votes
2answers
478 views

Is every knot unavoidable in the embeddings of some graph?

Is it the case that, for any given knot $K$, there exists some graph $G$ whose every embedding into $\mathbb{R}^3$ (or into $\mathbb{S}^3$) contains a cycle that realizes $K$? I know the ...
3
votes
1answer
208 views

How hard is a variant of graph automorphism problem?

I'm interested in a variant of graph automorphism problem (which is prime candidate for $NP$-Intermediate problem). Restricted GA Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ ...
0
votes
0answers
40 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
1answer
100 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'$. ...
4
votes
1answer
472 views

Surprising connection between linear algebra and graph theory

What is the intuition for linear algebra being such an effective tool to resolve questions regarding graphs? For example, one can determine if a given graph is connected by computing its Laplacian ...
0
votes
0answers
21 views

Splitting lemma for digraph and preserving local rooted-edge connectivity?

Let $G$ be a directed graph. $\lambda(x,y,G)$ is the maximum number of edge disjoint paths from $x$ to $y$ in $G$ The local $r$-rooted connectivity of $x$ in $G$ is $\lambda(r,x,G)$. The global ...
2
votes
1answer
121 views

Minimum length path touching $n$ circles

Given $n$ non-overlapping circles of radius $1$ (i.e., the distance between the centers of any two circles is greater than $2$), how to find the minimum length path (the path can be of any form) that ...
3
votes
0answers
39 views

Algorithm to construct metric space endomorphism with controlled square

Given a finite metric space $(M,d)$ with parameters $K \geq 1$ and $\epsilon > 0$, I'd like to algorithmically check for the existence of a non-identity map $\phi:M \to M$ which happens to be ...
0
votes
1answer
61 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 ...
2
votes
1answer
83 views

About the diameter of a graph after removing orientation

This question was posted a few days ago on the Mathematics StackExchange, but so far it has not been answered. Let $G$ be a strongly connected directed graph of diameter $D$, and suppose that we ...
4
votes
0answers
33 views

What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?

The Tutte polynomial is a bivariate polynomial with positive integer coefficient which is a graph invariant and can be defined recursively. Evaluating it is $\#P$-complete even when restricted to ...
1
vote
2answers
168 views

Strongly connected DAG from any connected undirected graph?

I have the following question. It seems likely to be true - can anyone provide a standard reference? Given: A connected, undirected graph. Question 1: Can we assume a single direction for each edge ...
7
votes
0answers
90 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 ...
3
votes
0answers
83 views

Node covering in a random graph

Given $N$ nodes randomly placed in a $D\times D$ area, i.e., the position of each node is randomly chosen. Assume that both $N$ and $D$ are sufficiantly large. An agent can move in the area at ...
0
votes
0answers
94 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
2answers
171 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
1answer
113 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
2answers
75 views

different way of selecting a random graph

Consider having a 'base' graph $G=(V,E)$ and selecting each vertex with independent probability $p$ and having the induced subgraph of $G$ with all 'selected' points as your random graph. Has this ...
0
votes
4answers
109 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 ...
3
votes
1answer
104 views

Graphs of lines on del Pezzo surfaces

Let $k$ be an algebraically closed field. To any del Pezzo surface $S$ over $k$ we may associate its graph of lines, which has one vertex for each line and an edge (with multiplicity if required) ...
2
votes
1answer
150 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 ...
0
votes
0answers
42 views

Paths on Cartesian products of graphs satisfying linear constraints

Assume integers $d > r > 0$ and a connected graph $G$ with $d$ vertices. Every point on the $r$-fold Cartesian product of $G$ with itself, $G^{\square r}$, is equivalent to a dimension-$d$ ...