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

1
vote
1answer
108 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
21 views

Min weight odd cycle with certain edge pairs forbidden

Given a weighted graph G=(V,E) and several disjoint sets $S_1 ,., S_t \subset E$ of edges is there a polynomial time algorithm to find a min weight odd cycle that does not contain more than 1 element ...
4
votes
1answer
96 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
92 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 ...
26
votes
1answer
873 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
147 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
98 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
29 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
59 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
627 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
171 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
105 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
65 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
118 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
48 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
158 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
40 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
152 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
118 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
292 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
32 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
119 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
61 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
13 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
124 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
144 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
66 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
97 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
1answer
206 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). ================= ...
0
votes
1answer
90 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
80 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 ...
7
votes
2answers
298 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
35 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
43 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
114 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
85 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
241 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 ...
1
vote
0answers
14 views

Path Sums in Arc Labeled st-graphs

My research has led me to a question on sums of integer labeled arc paths in an st-graph (single source single sink, acyclic, I actually have multi-graphs). The problem is to label all the arcs in a ...
7
votes
0answers
70 views

A separation property of graphs of bounded tree-width

The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2) Let $T$ be a tree and $r, m$ ...
0
votes
0answers
19 views

A Statement about a General Property of Negative Cycle Detection Algorithms

in this paper from 1999, the authors Boris Cherkassky and Andrew Goldberg state in the abstract that "The negative cycle problem is to find a negative length cycle in a network or to prove that ...
0
votes
1answer
44 views

Cycle-intersecting subsets

Let $G=(V,E)$ be a finite, simple, undirected graph. We call $D\subseteq V$ cycle-intersecting if for every simple cycle $C\subseteq V$ we have $C\cap D \neq \emptyset$. Is there a graph $G$ such ...
0
votes
1answer
51 views

What is the definition of size of an edge$?$

In page-$13$ of Graph minors. $X$. Obstructions to tree-decomposition, $\gamma(G)$ introduced as maximum size of an edge. What is the definition of size of an edge$?$ I think it may be number of edges ...
3
votes
1answer
59 views

What is the relation between Treewidth and Order of graph?

Can we say in general, Treewidth of every graph is less than or equal to number of vertices in that graph? Is there any other general relation between Treewidth and Order of graphs?
2
votes
1answer
45 views

What is the relation between Hadwiger number and Treewidth?

Is there any general relation between Hadwiger number and Treewidth of a graph? Intuitively I think Hadwiger number is greater than or equal to Treewidth, but I couldn't prove it.
4
votes
1answer
108 views

Which graphs are prime under the Cartesian product?

I'm looking for a characterization of graphs that are prime under the Cartesian product, with prime defined as in this question. Does such a characterization exist, either in general or after ...
4
votes
1answer
112 views

does every vertex-cut set in a maximal planar graph contain a cycle?

$G = (V, E)$ is a 3-connected plane triangulation. Let $S \subset V$ such that $G(V - S)$ is disconnected. Is it true that $G(S)$ must contains a separating cycle? My intuition is leading me to ...
1
vote
1answer
73 views

What is the relation between size of maximum clique and branchwidth?

Let $bw(G)$ be the branchwidth of graph $G$ and $\omega(G)$ be the size of maximum clique in $G$. I think the following inequality holds: $$ \omega(G)\leq bw(G) $$ Intuition: Assume (in reverse of ...
1
vote
0answers
42 views

Arithmetic progressions on a graph

Given $K_k$ a complete graph what is the minimum $n\in\Bbb N$ needed so that there is a map: $$f:\{0,1,\dots,n\}\rightarrow\mathsf{Edges}(K_k)$$ which makes every simple cycle to be $r$-term ...
0
votes
0answers
74 views

Variance of the average path length of connected graphs

The average path length has been defined for a connected graph $G$. It is defined here: https://en.wikipedia.org/wiki/Average_path_length Has the variance of these path lengths ever been ...
0
votes
0answers
61 views

Almost-hypohamiltonian Kneser Graphs

Here, it states that: When $n\ge 3k$, the Kneser graph $KG_{n,k}$ always contains a Hamiltonian cycle. Computational searches have found that all connected Kneser graphs for $n \le 27,$ except for ...