# Tagged Questions

**3**

votes

**1**answer

162 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

**0**answers

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

**5**

votes

**0**answers

85 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

**1**answer

93 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

**0**answers

70 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

**2**answers

84 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

**0**answers

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

**1**answer

110 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

**0**answers

24 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

**1**answer

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

**1**answer

93 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

**1**answer

882 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

**1**answer

148 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

**0**answers

100 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

**0**answers

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

**1**answer

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

**1**answer

631 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

**1**answer

176 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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

49 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

**1**answer

160 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

**1**answer

41 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

**2**answers

153 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

**1**answer

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

**0**answers

294 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

**0**answers

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

**3**answers

121 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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

99 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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

301 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

**1**answer

36 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

**0**answers

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

**3**answers

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

**2**answers

86 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

**4**answers

242 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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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?