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

3
votes
0answers
79 views

Is there a Havel-Hakimi for geometric graphs?

Suppose that we are given $n$ points in the plane, with a degree prescribed for each, and the question is whether we can place a geometric graph on them. Is there an efficient algorithm for this? ...
0
votes
1answer
74 views

Extremal problem: #paths of length l as function of number of edges

Suppose that $G$ is a simple, undirected graph with $n$ vertices and $m$ edges. Conjecture: The total number of vertex paths of length $l$ is at most $$ n (2 m/n)^{l-1} $$ The heuristic basis for ...
0
votes
0answers
82 views

Primitivity of $AA^\top$

Let $A\in\mathbb{R}^{n\times n}$ be a non-negative and irreducible matrix. Consider $B:=AA^\top$. It can be proved (I can post a proof if needed) that the following condition is necessary and ...
3
votes
2answers
153 views

Asymptotics of list size in Robertson-Seymour theorem

A planar graph cannot have $K_5$ and $K_{3,3}$ as minors. Robertson-Seymour theorem generalizes this by stating for every genus $g$ there is a finite list of forbidden minor graphs that are ...
1
vote
0answers
61 views

Building an orthogonal embedding for a 4-planar graph

I'm interested in the following paper http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf In particular i'm interested in the construction Valiant describes to prove that it is possible to ...
3
votes
1answer
172 views

A criterion for rooted trees to be isomorphic based on walks

Suppose you have two rooted trees $T_1$ and $T_2$ with roots $r_1$ and $r_2$, respectively. Furthermore, for every $k\ge 0$, the number of walks of $T_1$ starting at $r_1$ of length $k$ is equal to ...
1
vote
0answers
114 views

2-edge colorable graph approximation

A 2 edge-colorable graph is a graph in which we can color the edges with two colors, in a way such that no edges of the same color share a vertex. Given a graph G = (V,E) I want to find a 2 ...
6
votes
0answers
96 views

Is there a Ramsey theory for Kneser graphs?

Ramsey theory for graphs usually studies colorings of the edges of complete graphs. I'm interested whether there are any results about edge-colorings of Kneser graphs. More specifically, I'm most ...
2
votes
1answer
108 views

Bipartite dimension of an almost crown graph

A crown graph is a complete bipartite graph from which a perfect matching has been removed. The bipartite dimension of a graph is the minimum number of complete bipartite subgraphs needed to cover ...
6
votes
0answers
73 views

Contradicting claims about complexity of directed path graphs isomorphism

Thesis and a paper give conflicting claims about the complexity of graph isomorphism for directed path graphs. Since this means GI is polynomial likely I am missing something or there is something ...
-4
votes
2answers
94 views

Reconstructing a graph from the multiset of degrees

Suppose $G, H$ are finite, simple, undirected graphs and there is a bijection between the vertex sets $\varphi:V(G) \to V(H)$ such that for all $v\in V$ we have $$\text{deg}_G(v) = ...
0
votes
0answers
26 views

Name for a “Broken Cycles” Graph Problem

Is there a name for the task of reconstructing a set of cycles $\mathcal{C} = \{C_1,...,C_k\}$ in an undirected graph from the collection of $\mathcal{E}$ of edges constituting to $\mathcal{C}$, when ...
1
vote
1answer
113 views

diameter of Cayley graphs

For a group $G$ and an inverse closed subset $S$ of $G\setminus \{1\}$, the Cayley graph $Cay(G,S)$, is the graph whose vertices are the elements of $G$ and two vertices $x$ and $y$ are adjacent if ...
0
votes
0answers
34 views

Minimum weight odd cycle with certain edge pairs forbidden

Given a weighted graph $G=(V,E)$ and several disjoint sets $S_1, \dots, S_t \subset E$ of edges, is there a polynomial-time algorithm to find a minimum weight odd cycle which does not contain more ...
4
votes
1answer
111 views

Diameter vs Radius in Maximal Planar Graphs

Let $G$ be an undirected graph. The eccentricity of a vertex $v$ of $G$, is the maximum distance between $v$ and any other vertex of $G$:$\;\;$ $\mathit{ecc}(v) = \max_{u}\mathit{dist}(v,u)$. The ...
2
votes
1answer
131 views

Why is graph automorphism sometimes easier than canonical labeling (for current software)?

László Babai recently hinted that graph isomorphism is solved for all practical purposes: It seems, for all practical purposes, the Graph Isomorphism problem is solved; a suite of remarkably ...
28
votes
1answer
953 views

Should axiomatic set theory be translated into graph theory?

Recently I saw the abstract of a paper by Nash-Williams: ``Should axiomatic set theory be translated into graph theory?''. The abstract, taken from Mathscinet says the following: The author ...
1
vote
1answer
153 views

Conjecture of Kelly [closed]

In GTM 244,it writes: Two graphs G and H on the same vertex set V are called hypomorphic if, for all v ∈ V , their vertex-deleted subgraphs G − v and H − v are isomorphic.Does this imply that G and H ...
9
votes
0answers
103 views

Cycles of length $2^n - 2$ in the De Bruijn graph

It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$. ...
1
vote
0answers
31 views

Generate connected subgraphs as the satisfying assignments to a SAT instance

I want a SAT instance (in CNF) whose set of satisfying assignments are the connected subgraphs of a given input graph. A general solution would be helpful, but I really only need this when the input ...
-2
votes
1answer
65 views

Graph isomorphism for twin free graphs

Suppose you are given two graphs $G_1$ and $G_2$ and are promised that both are twin free. Is the problem of determining if they are isomorphic graph isomorphism hard? I am curious for the cases of ...
11
votes
1answer
676 views

Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?

In http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ it is mentioned: 'In discussing Johnson graphs, Babai said they were a source of “unspeakable ...
3
votes
1answer
199 views

Is there a version of Robertson-Seymour's graph minor theorem known to apply to signed graphs?

Here a signed graph is one where each edge is signed either odd or even. A cycle is odd or even according to the sum of the signs of its edges. For a given signed graph, a resigning may be performed ...
3
votes
1answer
107 views

Minimal number of vertices in a graph with special Hadwiger partitions

Let $G=(V,E)$ be a simple, undirected graph. We call a partition ${\cal P}$ of a non-empty subset of $V$ a Hadwiger partition if every block (member of ${\cal P}$) is non-empty and connected, and ...
-2
votes
1answer
66 views

Hadwiger partitions where one block is always a singleton

Let $G=(V,E)$ be a simple, undirected graph. We call a partition ${\cal P}$ of a non-empty subset of $V$ a Hadwiger partition if every block (member of ${\cal P}$) is non-empty and connected, and ...
2
votes
0answers
121 views

Which functions preserve the connectivity of graphs/components?

I am somewhat stuck working on an issue and would really love some guidance. I will state the problem, my current state and what led to it in case the solution lies beyond where I was looking The ...
2
votes
0answers
58 views

Blossoms and Colorings

There is a striking analogy between finding maximum matchings in graphs and determining the chromatic number of graphs: both problems are fairly easy for bipartite graphs, but harder, resp. too hard ...
2
votes
1answer
226 views

Can we solve Hamiltonian Path problem for biconnected planar graphs in linear time?

Assume that we have a bi-connected planar graph $G$ with $\Delta(G)>3$, and we want to find a Hamiltonian Path in $G$. As we know the st-order of a bi-connected planar graph can be computed in ...
2
votes
1answer
48 views

Bounds on chromatic index

Let $H$ be a hypergraph of maximum vertex-degree $\Delta$. (That is, for all vertices $x$, we have $| \{ e \in H \mid x \in e \} | \leq \Delta$) Are there any bounds on the chromatic index $\chi_e(H)$ ...
3
votes
2answers
164 views

on counting the number of trees on Kn (case)

During my reasearch I have stumbled across a problem that can be presented in such way: "How many are there spanning trees on Kn such that every tree contains v: deg(v) = k, for a given k" The ...
2
votes
1answer
135 views

Extremal combinatorics on bipartite graphs

One open question in extremal graph Theory is the so-called Zarankiewicz problem (see for instance the wikipedia page), which ask for the maximum number of edges in a bipartite graph with a fixed ...
9
votes
0answers
306 views

Is there an “Erlangen Program” for Graph Theory?

There are certain graph theoretic problems (especially optimization problems), whose solution-subgraph (i.e. the set of vertices and edges)), is invariant under certain modifications (especially ...
1
vote
0answers
34 views

Atomic parts of lexicographic products of vertex-transitive graphs

Suppose $H_1$ and $H_2$ are connected, vertex-transitive graphs, $H_1$ is not the complete graph, and $|V(H_2)| \ge 2$. Then, the lexigraphic product $G=H_1 \circ H_2$ is vertex-transitive, $0 < ...
1
vote
3answers
135 views

In what types of graphs can the maximum independent set be found in polynomial time?

I need to find the maximum independent sets of a serial of regular graphs, which is generally NP-complete. The wikipedia told me that this problem can be solved in polynomial time if the graph is ...
1
vote
1answer
62 views

Reduced echelon form of sparce matrices and constructing hash function

Let $G$ be a $d$-regular graph, and $A$ be the incidence matrix of $G$. Also suppose $B$ is a reduced echelon form of $A$ such that computations are in $\mathbb F_2$. Given matrix $B$, can we find ...
0
votes
0answers
14 views

Two-optimality of the Union of a Shortest Hamilton Cycle and a Minimum-weight Maximal Matching

let $G(V,E)$ be a complete, finite, symmetric and simple weighted graph with a unique shortest Hamilton cycle $T_{opt}(G)$ and a unique maximum matching of minimal weight $M_{opt}(G)$. Is it ...
3
votes
0answers
127 views

Finiteness for 2-dimensional contractible complexes

While thinking about graph-complex and related operadic stuff, I found a quite interesting (at least for me) question. However, I'm a novice in the algebraic topology, so I'm unable to resolve it by ...
5
votes
1answer
148 views

Generalisation of Kuratowski

So I've recently read the infinite graph version of Kuratowski's theorem. It says that a graph $G$ is planar if and only if the following three conditions holds: $|V(G)| \le |\mathbb{R}|$ $G$ has at ...
1
vote
1answer
68 views

Assigning random orientation to an edge in a regular graph

Given a simple regular graph of degree $d$ on $n$ vertices. Assume an ordering of vertices and assume all orientations of edges is from $i$ to $j$ if edges $ij$ exists and $i<j$. Pick $m$ random ...
-1
votes
1answer
106 views

Reducing chromatic number

(1) Is there an estimate for maximum number of edges in a $k$ colorable $v$ vertex $d$ degree graph with genus $g$? Call this $|E|$? (2a) What is a good estimate for worst case number of edges that ...
2
votes
0answers
43 views

Do product distributions (or graph products) eventually cluster as more products are taken?

Say we have a joint distribution on a finite alphabet $\mathcal{X}\times \mathcal{Y}$. It could be a communication link where we want to send a random message $X$ over a channel, but it gets garbled ...
2
votes
1answer
211 views

Proof that it's possible to colour all elements in set, that all subsets will be bicolored

(For my easy understanding, let me rewrite the question. The author should feel free to remove my edit or... accept it; I am leaving the original formulation at the end intact). ================= ...
1
vote
1answer
134 views

Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...
2
votes
1answer
83 views

“Hypo” and “Hyper” for Perfect Matching

There is a fairly rich classification on graphs with respect to the existence of Hamiltonian cycles either in unmodified graphs or after certain small modifications. Do there also exist such ...
8
votes
2answers
357 views

Densest Graphs with Unique Perfect Matching

Given a graph $G$ with $n$ vertices, that has a perfect matching $M$, what is the maximal number of edges that $G$ can have without contradicting the uniqueness of $M$? Are examples of such extremal ...
1
vote
1answer
40 views

Test Instances for Perfect Matchings in Graphs

Are there any graphs with a known set of perfect matchings and other predefined properties, such as vertex connectivity, which can be used for testing the implementation of matching algorithms? ...
0
votes
0answers
49 views

What is wrong with this isomorphism preserving transformation to a graph of bounded clique width and bounded rank width?

Got an isomorphism preserving transformation to a graph of bounded clique width and rank width. It, a paper and graphclasses.org imply graph isomorphism is in P, so likely something is wrong. Let $G$ ...
4
votes
3answers
130 views

Repository of graph classes that are tough to test non-isomorphic pairs from isomorphic pairs

(1) Which graph classes are extremely tough to test for graph non-isomorphic pairs from isomorphic pairs? (2) Is there a repository of adjacencies from such classes?
3
votes
2answers
121 views

Database of adjacency matrices on cospectral non-isomorphic graph pairs

Is there a repository of cospectral non-isomorphic graphs available somewhere? I am looking for list of $0/1$ adjacency matrix pairs that can be input data in tools such as MATLAB.
8
votes
4answers
259 views

Always a planar-drawn cycle through $n$ points

Given $n$ points in the plane, can we always find a cycle through all of them that has only straight line edges and no edges intersect (planar-drawn)? Intuitively the answer is yes, but I am ...