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

learn more… | top users | synonyms (1)

2
votes
1answer
29 views

Are there Similar Distance Binary Error Correcting Codes?

I'm trying to find a low distortion embedding of the trivial metric space into hamming space. It seems this should be doable by using a large set of low dimensional vectors, with approximately equal ...
1
vote
0answers
22 views

Favorable graph decomposition for dense graphs to solve independent set problem

I have to solve an independent set problem (ISP) on dense graphs with many cliques. To tackle the problem, I'm considering to use graph decompositions such as tree-, modular decomposition or ...
4
votes
0answers
42 views

Minimum equivalent digraph with respect to sources and sinks

Given a DAG (directed acyclic graph) $D$, with sources $S$ and sinks $T$. Find a DAG $D'$, with sources $S$ and sinks $T$, with minimum number of edges such that: For all pairs $u \in S, v \in T$ ...
2
votes
0answers
60 views

Assigning edge weights under shortest path constraints

We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping ...
-3
votes
0answers
48 views

A cubic simple graph without cut edges is matching covered [on hold]

I recently found the following exercise: Given a cubic, simple undirect graph G without cut edges then G is matching covered, i.e. every edge is contained in a perfect matching. My idea was that, ...
-1
votes
1answer
74 views

A sufficient condition for non existance of hamiltonian cycle

I think i have a sufficient condition for non existance of hamiltonian cycle in a graph, I want to check if it has already been found, I tried googling for it and didnt find anything so far, how can i ...
12
votes
0answers
182 views
+100

Reference for mixed graph acyclicity testing algorithm?

A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction ...
13
votes
4answers
211 views

Does the infinite graph of diagonals have an infinite component?

Suppose we connect the points of $V = \mathbb{Z}^2$ using the set of undirected edges $E$ such that either $(i, j)$ is connected to $(i + 1, j + 1)$, or $(i + 1, j)$ is connected to $(i, j + 1)$, ...
-2
votes
0answers
49 views

Fixed-length Representation of any subset of a set of points in some dimensional space?

Given some x data points in an N dimensional space, I am trying to find a fixed length representation that could describe any subset s of those x points? For example the mean of the s subset could ...
2
votes
1answer
353 views

Longest path in a DAG that's not too long

The problem I am interested in is a simple variant of the longest path problem on DAGs: find a path between two chosen vertices in a DAG such that the sum of the weights of its constituent edges is ...
5
votes
1answer
151 views

Complexity of k-clique for hypergraphs

Classic Problem: Let a number $k$ be given. The $k$-clique problem is as follows. Given a graph $G$, does there exist a subset $S$ of $k$ vertices so that any two vertices of $S$ are adjacent? ...
3
votes
1answer
186 views

Constrained version of vertex cover in a bipartite graph

Let $G(V_1, V_2, E)$ be a bipartite graph such that degree of all the vertices in $V_1$ is bounded by some constant (say) $d$. Now, for given two positive integer $l$ and $k$, we wish to decide if ...
1
vote
1answer
112 views

Graph classes with a “jump property”

Let us say that a graph class has the jump property, if it either contains all $n$-vertex graphs for every large enough $n$, or else the fraction of $n$-vertex graphs that belong to the class ...
7
votes
2answers
221 views

Number of Automorphisms of a graph for graph isomorphism

Let $G$ and $H$ be two $r$-regular connected graphs of size $n$. Let $A$ be the set of permutations $P$ such that $PGP^{-1}=H$. If $G=H$ then $A$ is the set of automorphisms of $G$. What is the ...
2
votes
0answers
107 views

Construction of a graph which has regular subgraphs at each iteration of a recursive process

I am studying Graph Isomorphism and also trying to figure out the complexity of a certain class of graph. The graph I am studying at the moment is described below Description : $G$ is a $r$ regular ...
10
votes
2answers
154 views

Can a hereditary graph class contain almost all, but not all, n-vertex graphs?

Let $Q$ be a hereditary class of graphs. (Hereditary = closed with respect to taking induced subgraphs.) Let $Q_n$ denote the set of $n$-vertex graphs in $Q$. Let us say that $Q$ contains almost all ...
2
votes
1answer
105 views

Perfect Matching with ``set-over-like" constraints?

Problem Description: Let k and n be some natural numbers. We are given a complete bipartite graph G where each side of G has n vertices. G is edge-labeled with labels being subsets of {1,...,k}. We ...
7
votes
1answer
193 views

Combinatorial discrepancy of the system of all cuts

This is a variant of this previous question. In the meantime I have learned that what I am really interested in is the discrepancy of the system of all cuts of the complete graph on $n$ vertices. More ...
4
votes
1answer
89 views

Minimum weight matching in general graphs with additional input specifying the number of matched edges

We know of the minimum weight perfect matching problem in general graphs which can be solved using a primal-dual algorithm. Assume, we have an additional constraint specifying the exact number of ...
3
votes
2answers
681 views

Finding the two shortest paths while minimizing the number of nearby/common edges

The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary. Consider the following variant: ...
4
votes
0answers
70 views

Random Sampling Threshold to Get a Connected Induced Subgraph

Working on network design this summer I have come across certain applications that have inspired me to ask the following question: Given an undirected connected graph $G=(V,E)$ what is the minimum ...
5
votes
1answer
85 views

Existence of certain graph gadget related to coloring odd hole free graph

Crossposted from MO. Wondering about the existence of graph gadget related to coloring (or 3-coloring) odd hole free graphs. Let $G$ be simple $k$-chromatic connected graph with two vertices $u,v$. ...
0
votes
0answers
62 views

Find the number of vertices that belong to all the maximum matchings of a general connected graph [duplicate]

The given graph is connected but not necessarily bipartite. Please describe the complete approach with useful links , I read stuff related to augmenting paths but could not comprehend well. An O(VE) ...
9
votes
2answers
128 views

Exact formula for the number of spanning trees of a rectangle

This blog talks about generating "twisty little mazes" using a computer an enumerating them. The enumeration can be done using Wilson's algorithm to get the UST, but I don't remember the formula for ...
1
vote
1answer
165 views

Two paper appear to imply collapse via coloring $P_5$-free graphs

Found this from graphclasses.org. Two papers give conflicting results for coloring $P_5$-free graphs which appear to imply $P=NP$. From Polynomial-time algorithm for vertex k-colorability of ...
2
votes
0answers
19 views

centralized deterministic Spanner construction with low degree and low stretch

Does there exist a centralized deterministic spanner construction with low degree and low stretch both independent of the graph diameter (no log D factor), but can be dependent on the number of nodes. ...
-2
votes
2answers
78 views

Is there a typo in this definition of Minimal Maximal Matching [closed]

in the following paper http://journal.frontiersin.org/article/10.3389/fphy.2014.00005/full the author describes the minimax problem as follows: Given a graph G = (V, E), we are looking for a ...
4
votes
0answers
73 views

Graph factors of maximum weight

I am trying to find references to a weighted version of the graph factor problem for the case when the "target degree" is a set of integers with "gaps" of size at most one. The unweighted version of ...
2
votes
1answer
150 views

Complexity of simple undirected graph isomorphism problem

We define a simple undirected graph as a graph where no vertex has a loop and there is only zero or one undirected, unweighted edge between any pair of vertices. My question: What is the complexity ...
11
votes
2answers
340 views

Number of vertices present in all maximum matchings

Given a graph $G$, we need to find the cardinality of the largest set of vertices so that each of them are present in every maximum matching possible. Is there a solution beside the obvious remove ...
2
votes
1answer
94 views

Finding a random regular graph with degree d

I'm trying to find undirected random graphs $G(V,E)$ with $|V|$ = $d^2$ for $d \in \mathbb{N}$ such that $\forall v \in V: deg(v) = d$. For $d \in 2\mathbb{N} +1$ this trivially is impossible as no ...
0
votes
1answer
99 views

How many edges are cut in a balanced partition of a graph?

Consider a graph on n nodes and e edges that is partitioned into k "balanced" subgraphs in the sense that each block has an equal number of nodes and the number of cut edges is minimized. Is there a ...
1
vote
1answer
74 views

Finding all possible simple cyclic paths in a digraph

I have a strongly connected component with over 200 vertices and more than 600 edges. I need to iterate through each simple cycle in the graph exhaustively, without specifying a particular node. Is ...
6
votes
1answer
92 views

Lexicographic perturbation for euclidean shortest path instances?

Assume we have an undirected graph $G=(V,E)$ and vertex locations $\pi: V \rightarrow \mathbb{R}^2$. I am looking for a procedure to perturb the vertex positions to obtain new positions $\pi'$ such ...
16
votes
0answers
236 views

$\Delta = 57, d=2$ Moore Graph

I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years. You may recall that Hoffman and ...
14
votes
1answer
290 views

How expensive may it be to destroy all long s-t paths in a DAG?

We consider DAGs (directed acyclic graphs) with one source node $s$ and one target node $t$; parallel edges joining the same pair of vertices are allowed. A $k$-cut is a set of edges whose removal ...
3
votes
0answers
92 views

How many neighbors does a vertex has which are closest to a source vertex in random regular graphs?

Let $G=(V,E)$ be an undirected, random $r$-regular graph. Let $s,t\in V$, and denote by $N(v)=\{u\in V\mid (u,v)\in E\}$ the neighborhood of $v$. I'm looking for the distribution of the number of ...
5
votes
1answer
180 views

$d$-regular bipartite expander graph

I have seen that there exists $d$-left regular bipartite graphs. My question is do there exists $d$-regular bipartite expander graphs in which both the degree of the left and the right vertices is ...
12
votes
1answer
227 views

Does treewidth $k$ imply the existence of a $K_{1,k}$ minor?

Let $k$ be fixed, and let $G$ be a (connected) graph. If I'm not mistaken, it follows from the work of Bodlaender [1, Theorem 3.11] that if the treewidth of $G$ is roughly at least $2k^3$, then $G$ ...
1
vote
0answers
65 views

Matrix of ranking

In any graph of n nodes in any dimension, define matrix $M_r$ of ranking as $\forall r_{ij}\in M_r$, $r_{ij}$ is the ranking of j to i. That is, j is the $r_{ij}$th nearest node to i. Therefore, any ...
12
votes
1answer
269 views

Structure of graphs that exclude a perfect matching on four vertices as an induced graph

I am interested in understanding the structure of the class of graphs $G$ such that there is no vertex induced subgraph on four vertices that is a perfect matching. Stated differently for any four ...
0
votes
1answer
71 views

Calculate sum of reciprocal rank in arbitrary large graph

For arbitrary graph of n node, can I approximate $\sum_{v\neq u}\frac{1}{Rank_u(v)^a\times Rank_v(u)^b}$ with $\sum_{v\neq u}\frac{1}{Rank_u(v)^{a+b}}$ or not when n is large enough? $a,b>0$, ...
6
votes
0answers
90 views

Edge-partitioning into rainbow triangles

I'm wondering if the following problem is NP-hard. Input: $G = (V,E)$ a simple graph, and a coloring $f : E \to \{1,2,3\}$ of the edges ($f$ does not verify any specific property). ...
3
votes
1answer
94 views

Partitioning the edges of a complete graph into smaller complete graphs

Consider the (simple, undirected) complete graph $K_n$. Is it possible to partition its edges into less than $n$ cliques, each having less than $n$ vertices? Note: It is easy to see that $n$ cliques ...
4
votes
1answer
253 views

Counting the number of K4

I was going over this paper and I don't understand a certain proof (section five phase 2). Given a graph G=(V,E) partitioned into the sets of vertices L and H. The vertices in L are at most D where D ...
0
votes
0answers
40 views

Approximate distance preserving sparse graph representation that are not necessarily subgraphs

I am looking for a type of graph sparsifier that I think I have seen somewhere but now I can't find the paper anymore. I think the paper referred to it as a spanner, but that term is used for so many ...
5
votes
1answer
254 views

Sparser Bipartite graphs?

Maximal Planar Bipartite graphs are sparser than maximal planar graphs. For which other classes of graphs are maximal Bipartite members sparser than arbitrary maximal members. Let $\mathcal{C}$ be a ...
3
votes
2answers
173 views

Runtime of Tucker's algorithm for generating a Eulerian circuit

What is the time complexity of Tucker's algorithm for generating a Eulerian circuit? The Tucker's algorithm takes as input a connected graph whose vertices are all of even degree, constructs an ...
0
votes
1answer
82 views

TSP heuristics for limited distance information

this is my first question on Theoretical CS. :) I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site. Problem: I'm looking for TSP ...
0
votes
0answers
36 views

Characterization of an irreducible matrix

A matrix is irreducible, if it is not similar via some permutation to a block upper triangular matrix that has more than one block of positive size. Equivalently, for a 0-1 matrix, if it is viewed as ...