# Questions tagged [graph-theory]

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

1,535 questions
Filter by
Sorted by
Tagged with
44 views

### d-regular graphs and edge expanders

Show that there is no (n, d, ρ)-edge expander for ρ > 0.5 Is this statement even true? My attempt: Let n = 2, then we can have 2 vertices, A and B. Let d = 1, therefore there is an edge between A ...
49 views

### Average case complexity of decision version of NP-hard problem

I am a bit confused regarding the average case complexity of certain graph problems that are NP-hard like graph coloring, clique, dominating set and whose decision version is NP-complete. It is ...
15 views

### Any value in a formula that calculates (not look up) the 'order' of a 'Independent Edge Set' OR a 'I.E.S.' given an 'order' on complete graphs?

Any value or interest in a formula that calculates (not look up) the 'integer order' of a given 'Independent Edge Set' OR given an 'Independent Set' calculates the 'integer order' on Complete Graphs? ...
• 1
72 views

### Name for a cyclic path in a graph that visits every vertex while minimizing the maximum number of times a given vertex is revisited?

Me and my colleague are interested in whether anyone has looked into a generalization of Hamiltonian cycles where vertices can be revisited, but we want to minimize the maximum number of times a given ...
• 429
74 views

• 2,164
1 vote
60 views

### Graphs such that every rotation system admits an embedding on a surface of small genus

Let $G$ be a finite, simple, undirected graph. What conditions on $G$ ensure that every rotation system of $G$ corresponds to a cellular embedding of $G$ on an oriented surface of small genus? (e.g. ...
• 1,723
1 vote
45 views

### Given several $a_i$-$r$ paths in a planar graph how balanced" of a tree rooted at $r$ can I make?

Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and several $a_i$-$r$ paths $P_i$ in a planar graph $G$. I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ that minimizes the ...
• 186
1 vote
38 views

### Asking boolean question on the nodes of a DAG to find the target node

We are given a DAG $G=(V, E)$ and an unknown target node $x \in V$ to find. There is a mechanism to probe a node, $y \in V$, to ask question of the form "Given the node $y$, is the target node $x$...
109 views

### Cover all triangles of a graph with n subgraphs as small as possible

What is the smallest number $s(n,\Delta)$ such that for any undirected simple graph $G=(V,E)$ with $n$ vertices and $\Delta$ triangles, there exist $n$ subgraphs of $G$ covering all triangles where ...
• 63
136 views

### Finding the shortest cycle containing a vertex in a graph

Given a connected undirected graph with edges $E$ and verticies $V$ and a vertex $v \in V$, find the length of the shortest cycle containing $v$. The best I could do is $O(|E|*deg(v))$, by trying to ...
84 views

### (Where) is determining the mixing time of an implicitly defined graph in the polynomial hierarchy?

Consider an implicitly defined graph; for example, let $G$ be a finite group generated with $n$ generators as $\langle g_1,g_2,\ldots g_n\rangle$ and let $\Gamma$ be the Cayley graph of $G$ under ...
• 1,063
35 views

• 141
200 views

### Cover a graph with complete graphs

I want to find the smallest possible function $k(n,m)$ such that for any graph $G$ with $n$ vertices and $m$ edges, there exists $n$ vertex sets $S_1,S_2,...,S_n\subseteq V$ each with size $k(n,m)$ ...
• 63
1 vote
37 views

### Minimum vertex-separators under edge addition

I am trying to prove the following claim. Let $T$ be a minimum $st$-separator in an undirected graph $G$, and let $x \in T$. Let $S\neq T$ be a minimal $st$-separator (i.e., not necessarily minimum), ...
• 95
129 views

### Complexity of induced Steiner Tree problem

Consider the following problem: we are given an undirected graph $G=(V,E)$ and three terminal vertices $t_1,t_2,t_3\in V$. We are asked whether there exists a set of vertices $S\subseteq V$ such that ...
• 3,416
180 views

### Two graphs indistinguishable by 4-WL

There are pairs of non-isomorphic graphs that are indistinguishable by the k-WL (but distinguishable by (k+1)-WL) [1]. For example 4x4 rook’s graph and the Shrikhande graph are non-isomorphic but the ...
• 61
77 views

### increasing minimum graph degree by adding edges

My problem: Given a graph $G=(V, E)$ and an integer $\ell$,add a minimum number of edges to $G$ so that in the resulting graph every vertex has degree at least $\ell$. Is there a polynomial-time ...
• 33
159 views

### Treewidth for hypergraphs that specify connectedness requirements

This question is about an alternative definition of treewidth, called weak treewidth. It is defined on hypergraphs where hyperedges intuitively require that the connected subtrees of occurrences of ...
• 8,896