# Tagged Questions

**1**

vote

**0**answers

98 views

### The lattice of graphs under vertex abstractions

I am curious to know if the following structure has been studied, or if anything similar is in the literature.
For $n \in \mathbb{N}$, let $G = ([n],E)$ be a digraph. A partition of a subset $V$ of $[...

**2**

votes

**0**answers

112 views

### Detecting Negative Cycles in Undirected Graphs

I recently faced the problem of quickly detecting negative cycles in undirected, weighted graphs. Resorting to the Bellman-Ford Algorithm, as commonly suggested, turned out to be very inefficient and ...

**0**

votes

**0**answers

16 views

### Does this transformation graph to multigraph keeps some (multi)graph invariants related?

Consider the following transformation graph $G$ to multigraph $G'$.
$V(G')=V(G)$.
For the edges of $G'$ add a clique of $V(G')$. For each
edge $e \in E(G)$ add parallel edge $e'$.
So $G'$ is clique ...

**3**

votes

**0**answers

75 views

### Graph adjacency grouping with geometric criteria

I start with a list of adjacent tetrahedra, where there are tight seals to one another along faces for two tetrahedra that are adjacent. The vertices belonging to these faces for both tetrahedra are ...

**-3**

votes

**2**answers

149 views

### Does every 3-regular bridgeless graph have a perfect matching? [closed]

Let $G$ be a simple $3$-regular (every vertex has degree $3$) $2$-edge connected graph. Does $G$ contain a perfect matching?

**0**

votes

**0**answers

21 views

### Complexity of computing the multivariate Tutte polynomial of clique where each edge have distinct label

The multivariate Tutte polynomial $Z_G(q,v)$
is generalization of the Tutte polynomial and each edge is labelled by
variable $v_e$.
$Z_G(q,v)$ is linear in $v_i$.
Let $G$ be a clique where each edge ...

**1**

vote

**0**answers

20 views

### Complexity of computing the Tutte polynomial of multigraph when the Tutte polynomial of the underlying simple graph is known

Let $G$ be multigraph with $l$ loops and $m$ multiple edges and $G'$ be the
underlying simple graph (loops and multiple edges removed).
Assume the Tutte polynomial of $G'$ is given.
Q1 What is ...

**1**

vote

**0**answers

37 views

### Non-adjacent Pair of Edges with Minimal Weight Sum

Given an weighted, undirected Graph $G(V,E)$ without loops or parallel edges,
what is the complexity of determining a pair of non-adjacent edges, whose sum of weights is w.l.o.g. minimal?
...

**2**

votes

**1**answer

120 views

### Name for the set of vertices with the same neighborhood as another vertex

Suppose $\Gamma$ is a simple graph and $N_{\Gamma}(g)=\{x\in V(\Gamma)|x\sim g\}$ is the neighborhood of $g\in V(\Gamma)$. Then consider
$$\mathbb{S}=\{y\in V(\Gamma)|N_{\Gamma}(y)=N_{\Gamma}(g)\}.$$
...

**1**

vote

**0**answers

26 views

### Some confusion regarding the definition of NPO reduction

I've seen the following definition in a paper on approximation preserving reductions.
Definition:Let $\pi_{1}$ and $\pi_{2}$ be two NPO maximization problems. Then we say that $\pi_{1} \leq_{R} \pi_{...

**2**

votes

**1**answer

87 views

### Orthogonal embeddings and edge lengths

I'm interested in orthogonal embeddings of graphs into the 2-dimensional, i.e where vertices are placed at integer co-ordinates and edges are routed along the grid lines and are not allowed to ...

**0**

votes

**1**answer

60 views

### Reference Request: Graph Edge Density

I was curious if there was a reference which answers the question, What is the maximum number of edges in a graph $G$ with $n$ vertices which does not contain a $5$-cycle? $k$-cycle? The analogous ...

**2**

votes

**0**answers

111 views

### Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.
The answer ...

**2**

votes

**1**answer

70 views

### Minimum Edge Density given a particular condition

Consider a graph with $n$ vertices such that if one takes any 4 vertices there are at most 4 edges among these 4 vertices (Notice that there are 6 "possible" edges among these 4 vertices). What is the ...

**3**

votes

**1**answer

209 views

### Variants of Szemeredi's regularity lemma

I've noticed that the name 'Szemeredi's regularity lemma' is used for several closely related yet different statements about graphs.
Specifically, I'm interested in the distinction between two of ...

**2**

votes

**1**answer

189 views

### Existence of Spanning Tree implies Well Ordering Principle

Every connected graph has a spanning tree.
Every non-empty set can be well ordered.
Basically I am trying to show that statement 1 implies statement 2. What I tried is as following:
Let $X \ne \...

**4**

votes

**1**answer

132 views

### Edge Reconstruction Conjecture

I have seen this question asked at least once before, but not with any real answers.
I was reading about the various reconstruction conjectures and equivalents, and I saw that the reconstruction ...

**3**

votes

**0**answers

80 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

**1**answer

78 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

**0**answers

83 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

**2**answers

158 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

**0**answers

67 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

**1**answer

175 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

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

**6**

votes

**0**answers

99 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

112 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

76 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

96 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) = \deg_H(\varphi(v)).$...

**0**

votes

**0**answers

27 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

114 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

35 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

121 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

162 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

**1**answer

966 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

154 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

106 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

32 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

66 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

704 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

208 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

109 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

67 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

122 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

68 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

246 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

50 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

169 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

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

**8**

votes

**0**answers

315 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

35 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 < \...