Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,451
questions
3
votes
0answers
199 views
Power law for degree distribution of random KNN graphs?
Setup Sample random points from say standard Gaussian (or uniform) distribution in $R^{d}$ for some "d"
and consider a KNN (K-nearest neigbour) graph for some K.
Look at the degree ...
0
votes
0answers
95 views
How many maximal planar graphs are there?
We denote by a triangulation a (simple) maximal planar graph. How many triangulations on $n$ vertices are there? How many triangulations are there if we cannot distinguish the vertices, i.e. ...
0
votes
1answer
149 views
Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$
Let $G=(V,E)$ be a random $\Delta$-regular graph with $\Delta \in \Theta(\sqrt{|V|} \log^2 |V|)$. I'm analysing an algorithm having asymptotic running time crucially depending on the Independence ...
3
votes
1answer
75 views
Generating hard satisfiability problems with given constraint graph
Is there a systematic way to tune the hardness of a set of satisfiability problems (say 3-SAT or MAX2SAT) where the constraint graphs are always embeddable into a fixed given graph?
2
votes
0answers
65 views
Can we always find a graph with a given algebraic connectivity?
This is crossposted from math stackexchange. This is my first time posting here, so let me know if I'm doing something wrong.
I would like to experiment with various spectral properties of graphs, ...
1
vote
0answers
46 views
Dynamic permutation cycle data
Let $\pi \in S_n$ be a permutation of $\{1, \ldots, n\}$. Does there exist a simple data structure that admits the following operations in polylogarithmic time?
sameCycle($\pi,x,y$): determines ...
0
votes
1answer
85 views
How many more colours do you need if you add to $G$ a maximum matching from $G^c$?
The title says it all. Let $G$ be a (simple undirected finite) graph, and let $G^c$ be the complement of $G$ (i.e. contains edges not in $G$ and no more). Let $M$ be a perfect matching in $G^c$.
How ...
3
votes
2answers
145 views
Coloring where all colors are present in closed neighborhood of every vertex
I am interested in (proper) vertex colorings of graphs with the following condition:
for every vertex $v$ in the graph, all colors should be present in the closed neighborhood of $v$.
Is this studied ...
0
votes
0answers
51 views
How and How fast can we infer a logical formula that expresses a given graph in C$^2$( logic with 2 vars and counting quantifiers)?
In the following paper the author's claim that almost all graphs can be expressed in first order logic with counting quantifiers and two variables.
I would like to know, is there any algorithm that ...
7
votes
1answer
117 views
Extending cographs with product operation
Let $\mathcal{C}$ be the class of undirected graphs defined inductively as follows:
A single vertex is in $\mathcal{C}$;
If $G\in\mathcal{C}$ then its complement $\overline{G}$ is in $\mathcal{C}$;
...
2
votes
0answers
126 views
Finding nodes with enough unique ancestors
Given a DAG $G = (V, E)$, let $T \subseteq V$ be a set of nodes of $V$ that is computed via the following process. Assuming the nodes of $G$ are sorted in topological order, $v_1, \dots, v_n$. We ...
2
votes
1answer
142 views
Is this homework problem on T-joins wrong? [closed]
In Question 9.3a, it states that if $T=V$, then the minimum cost perfect matching is the minimum cost T-join. Is this actually true? I think I have a counterexample which I have drawn below.
10
votes
1answer
280 views
The number of clauses in an unsatisfiable CNF
I am interested in generalisations of the following observation:
An unsatisfiable $k$-CNF has at least $2^k$ clauses.
A special case of the observation is when $k=n$, where $n$ is the number of ...
1
vote
1answer
73 views
Separating DAGs using separators consisting of lists of nodes and all ancestors
Suppose we are given a DAG, $G = (V, E)$ where $n = |V|$. We consider the sets $J_1, J_2, \dots, J_n$ to be lists of vertices where list $J_i$ consists of vertex $v_i \in V$ and all ancestors of $v_i$....
1
vote
0answers
37 views
Remove cycles from a stochastic comparison matrix, while doing the least amount of editing
Let $\mathcal P_n$ be the collection of all matrices $M \in [0, 1]^{n \times n}$ such that $M_{ij} + M_{ji} = 1$ for all $i, j \in [n]$. Such matrices are called comparison matrices. A comparison ...
1
vote
0answers
53 views
Three Clique Sums of Bounded Treewidth and Bounded Genus graphs
This question asks about the forbidden minors of the class of graphs that can be formed by taking three clique sums of planar graphs and bounded treewidth graphs(The class is defined for some constant ...
2
votes
0answers
17 views
Power of Hyperedge Replacement Grammars (HRGs)
Can HRGs generate languages which equal or include the following graph languages:
All (bipartite) graphs of bounded degree
All (bipartite) planar graphs of bounded degree
All (bipartite) planar ...
2
votes
1answer
95 views
A conjecture on 4-coloring maximal planar graphs
The question/task is to prove/disprove the conjecture below.
Let $G$ be a maximal planar graph with a 4-coloring $f$. Let $(a,b,c,d)$ be a cycle in $G$. Let $S$ be the collection of all $a,c$-paths in ...
3
votes
1answer
224 views
Two different graph densities: $|E|/|V|$ and $|E|/(|V|-1)$
Let $G=(V,E)$ be a graph.
Let $m(G)=|E|$ and $n(G)=|V|$.
There are two different density definitions for $G$:
$$d_1(G)=\frac{m(G)}{n(G)}$$
and
$$d_2(G)=\frac{m(G)}{n(G)-1}.$$
Let $H^* \subseteq G$ be ...
9
votes
0answers
83 views
Forbidden Subgraph Characterization for Graphs with few Maximal Cliques
Consider the following property of undirected graphs. A graph has the $s$-vertex overlap property if every vertex is contained in at most $s$ maximal cliques. I am interested in forbidden induced ...
3
votes
1answer
127 views
Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph
So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices.
In general case, it is exponential.
I am trying to determine whether the ...
5
votes
1answer
97 views
Upperbound for max degree of k-tree completion
Definitions: For a graph $G$, a $k$-tree completion of $G$ is a $k$-tree obtained by adding edges to $G$ (if $G$ has a $k$-tree completion, $G$ is said to be a partial $k$-tree). The least integer $k$ ...
3
votes
0answers
107 views
Minimum feedback arc set for dense directed graph
This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $A$ and permutation matrix $P$, where we define $\tilde{A}:= PAP^T$. I want to pick $P$ such that if $\...
5
votes
1answer
93 views
Series-parallel DAG characterization
According to this Wikipage series-parallel graphs are characterized like this:
2-connected series-parallel graphs are characterized by having no subgraph homeomorphic to $K_4$.
I couldn't find a ...
3
votes
1answer
100 views
Decomposing Single Crossing Minor Free graphs
We know that for a single-crossing graph H of size h, there exists a constant ch whose value depends only on h, such that every four-connected component of an H-minor-free graph is either a planar ...
4
votes
0answers
84 views
Complexity of Encoding a Matroid Flow Problem in a Matrix
Context:
Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$.
We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
1
vote
0answers
56 views
Complement of Multi-colored Clique with an extra condition
In the problem Multi-colored clique, we ask for a $k$-clique of the input graph $G$ where $G$ is guaranteed to be $k$-colorable. In the complement problem Independent Set given Clique Partition, we ...
5
votes
1answer
82 views
Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$
Let $G=(V,E)$ be graph. Recall that a cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in ...
2
votes
1answer
148 views
Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices
I am interested in the MulitColoredClique problem with an additional restriction.
(Def.: A $k$-coloring $V_1,V_2,\dots,V_k$ of a graph $G$ is a partition of the vertex set of $G$ into $k$ independent ...
6
votes
0answers
118 views
Computational complexity of finding paths with specified product in a (group-labeled) directed graph
This question came up in the analysis of the puzzle game Swish. One way of representing the solvability problem is this: given a directed graph $G$ where each edge of the graph is labeled with an ...
0
votes
1answer
143 views
Graphs-like data structure with weighted vertices
I am searching for literature related to a graph-like data structure where vertices are weighted instead of edges.
Formally, we can define a weighted-(edge)-graph $G=(V,E, w(\cdot))$ as a tuple of ...
5
votes
1answer
409 views
Isomorphic graph embeddings in the Euclidean Space
Given an undirected and unweighted graph $G = (V, E)$, is it possible to find a mapping $f: V \rightarrow \mathbb{R}^k$ for some $k$ such that for every $i, j \in V$, $\|f(i) - f(j)\|_2^2 = \Delta(i, ...
-1
votes
1answer
82 views
Al-Mubaid's Similarity Measure for Ontological Concepts
Al-Mubaid et al. proposed a semantic similarity measure in their research paper [1]. They see ontologies as connected graphs but refer to clusters within ontology graphs without ever defining what ...
2
votes
1answer
109 views
Complexity of acyclicity of a "nondeterministic" graph
By "nondeterministic" I mean the graph is a collection of sets of "candidate" edges sharing a single destination: $E \subseteq 2^V \times V$. The problem is whether it is possible ...
2
votes
1answer
211 views
MaxCut instance with smallest max cut
Let us look at all 4-regular undirected graphs with $n$ nodes and edge weight equals to 1 for all edges. Out of these graphs, I would like to find the MaxCut instance with least number of edges in its ...
1
vote
0answers
223 views
Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?
In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the ...
5
votes
1answer
179 views
Complexity of finding the most likely edge
Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes.
Now consider the following random process. First sample a uniformly random ...
0
votes
1answer
92 views
Sample graph dataset for testing algorithms
I hope I'm addressing the right community. For a project for my students, I need to find some weighted graphs (oriented or not) to benchmark their algorithms (shortest paths, flows...).
There are a ...
1
vote
0answers
43 views
Minimum graph cycle basis respect to non-empty pairwise intersection of cycles
I'm trying to understand the following problem if anyone can help I'll be very grateful
Instance: undirected, unweighted, connected graph graph $G=(V,E)$.
Question: find a minimum cycle basis $B = \{...
2
votes
0answers
52 views
The Edge Cover Equilibrium Problem
Let the Edge Cover Equilibrium Problem be the following:
INPUT: a simple undirected graph $G$.
OUTPUT:
YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
1
vote
0answers
99 views
Is the edge cover polytope integral on graphs with self-loops?
It is well known that the edge cover polytope is integral on simple graphs. I am wondering whether this also holds for graphs with self-loops.
Here is a Linear Relaxation of the edge cover polytope, ...
0
votes
0answers
121 views
Comparing two graphs when starting from a single edge
Let's assume that we are given two graphs $G_1$ and $G_2$ defined by the two following nicely drawn pictures. Black numbers label the nodes, red numbers show the edge weight between the nodes.
$G_1$ ...
3
votes
1answer
187 views
Isomorphism preserving transformation CNF to Graph?
In short we are interested in isomorphism preserving
transformation CNF to Graph.
Let $\phi_1,\phi_2$ be CNF formulas.
Define $\phi_1$ and $\phi_2$ to be isomorphic $\phi_1 \cong \phi_2$
if there ...
1
vote
0answers
149 views
Is the matching polytope integral?
In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf
they prove the integrality of the matching polytope using the integrality of the perfect matching polytope.
The ...
4
votes
1answer
140 views
Neighborly properties in a bipartite graph
Input: Let $G$ be a connected, bipartite graph with parts $A$ and $B$, each of size $n$. For a set of vertices $S$, let $N(S)$ be its set of neighbors.
Question: Decide whether there exists a subset $...
3
votes
0answers
141 views
Uniquely 4-colorable Planar Graph Conjecture?
My question is on Uniquely 4-colorable Planar Graph Conjecture mentioned in
On purely tree-colorable planar graphs (and other papers of same(?) team such as "Theory on Structure and Coloring of ...
1
vote
0answers
46 views
Non-rigid isomorphic structures
In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ...
1
vote
1answer
140 views
On the paper "Quantum Computing Hamiltonian cycles"
The paper Quantum Computing Hamiltonian cycles claims:
An algorithm for quantum computing Hamiltonian cycles of simple,
cubic, bipartite graphs is discussed. It is shown that it is possible to
evolve ...
4
votes
2answers
379 views
3-colourability of Eulerian maximal planar graph
The following paragraph is from this answer by David Eppstein (emphasis mine).
A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single ...
2
votes
1answer
127 views
Who proved that a triangulation is 3-colourable implies its dual is bipartite
Let $G$ be a maximal planar graph (also called a triangulation); i.e, $G$ is a planar graph every face of which is a triangle. It is well known that the following three statements are equivalent:
(i) $...