# Questions tagged [graph-theory]

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

1,319 questions
Filter by
Sorted by
Tagged with
916 views

### Online transitive closure better than O(N^2) per edge addition

I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this: ...
662 views

### Complexity of recognizing vertex-transitive graphs

I am not knowledgeable in the area of complexity theory involving groups so I apologize if this is a well known result. Question 1. Let $G$ be a simple undirected graph of order $n$. What is the ...
756 views

### Reference for (odd-hole,antihole)-free graphs?

X-free graphs are those that contain no graph from X as an induced subgraph. A hole is a cycle with at least 4 vertices. An odd-hole is a hole with an odd number of vertices. An antihole is the ...
398 views

### Strongly Regular Graph and GI-Completeness

It is not known if graph isomorphism (GI) for strongly regular graphs (SRGs) is in P. Are there any hints that it might or might not be GI-Complete? Are there any strong consequences in such cases? (...
678 views

### Making a minimum-width tree decomposition lean in polynomial time

As is well known, a tree decomposition of a graph $G$ consists of a tree $T$ with an associated bag $T_v \subseteq V(G)$ for each vertex $v \in V(T)$, which satisfies the following conditions: Every ...
954 views

### Number of Hamiltonian cycles on random graphs

We assume that $G\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n}$. Then the following fact is well known: \begin{eqnarray} Pr [G\mbox{ has a Hamiltonian cycle}]= \begin{cases} 1 & (c(n)\...
1k views

### NP-hardness of a graph partition problem?

I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic? Here $E$ is ...
435 views

### What is the complexity of this graph problem?

Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that for any vertex $x\in A$ at least half of the neighbors of $x$ are also in $A$, and the size of $A$ is ...
544 views

### Sensitivity of Graph Properties

In , Turan shows that the sensitivity (called "critical complexity" in the paper) of a graph property is strictly greater than $\lfloor {1\over 4} m \rfloor$ where $m$ is the number of vertices in ...