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

learn more… | top users | synonyms (1)

1
vote
0answers
63 views

Graph sparsification

I would like to ask if any one is aware of any results related to graph sparsification with bounded degrees? What I mean is anyone aware of graph sparsification results such that the resultant graph ...
-5
votes
0answers
21 views

doubt regarding power of graph [on hold]

could you help me in clarifying a doubt regarding how to find square of a graph g from graph g.the doubt occurs on 15th page of the document which I have shown you by the link given.the doubt is that ...
-5
votes
0answers
21 views

please explain in simple terms simrank [on hold]

please explain in simple terms the concept of simrank.I have to take a seminar on simrank but I couldn't get the mathematical equations that point to this topic.
-2
votes
0answers
44 views

MSO logic for graph connectivity

Can connectivity of a graph be expressed in MSO logic so that Courcelle's Theorem can be applied?
-1
votes
0answers
40 views

minimum weighted subgraph of a weighted complete graph

i have a complete weighted graph G with n vertices. i need to find an induced subgraph S of G with k vertices such that the weight should be global minimum
0
votes
0answers
55 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
4
votes
2answers
169 views

Algorithms for online clique detection

Are there any algorithms which let you detect cliques when adding/deleting edges based on previously detected cliques? What would be the time/memory complexity of this approach?
-1
votes
0answers
67 views

Cut-vertices between two given vertices in a DAG [closed]

Assume that we are given a directed acyclic graph. Given two vertices $v$ and $u$ we want to find all cut vertices between them. A vertex $x$ is a cut vertex we between $v$ and $u$ iff $u$ is ...
6
votes
2answers
171 views

Partition planar graph into connected subgraphs of equal size

Work Jünger, Michael, Gerhard Reinelt, and William R. Pulleyblank. "On partitioning the edges of graphs into connected subgraphs." Journal of graph theory 9.4 (1985): 539-549. states that for ...
-2
votes
1answer
62 views

Communities in a graph [closed]

While studying about communities in a graph, i was curios regarding any algorithm which deals with projection of these communities in 2D/3D plane. Most of the algorithm i have studied were related to ...
11
votes
1answer
284 views

Existence of long induced paths in expander graphs

Let's say that a graph family $\mathcal{F}$ has long induced paths if there is a constant $\epsilon > 0$ such that every graph $G$ in $\mathcal{F}$ contains an induced path on $|V(G)|^{\epsilon}$ ...
9
votes
0answers
111 views

Maximum local edge connectivity

For a simple graph, the local edge connectivity of vertices $x,y$ where $x\neq y$ is $\lambda(x,y)$ and defined as the maximum number of edge disjoint paths from $x$ to $y$. One can find this by a ...
3
votes
1answer
89 views

Is there a known extension of Dirac's / Ghoulia-Houri's theorems for $k$-path existence?

In the well studied problem of Hamiltonicity, several papers/theorems gave sufficient "degree conditions" for the existence of Hamiltonian path in a graph. These include: Dirac's theorem , 1952, ...
9
votes
0answers
123 views

Is RAMSEY COLORING in $NC$?

Say that a function $f$ is a RAMSEY COLORING if on unary input $n$, it returns a complete graph on $n$ vertices with its edges colored red and blue without a monochromatic clique of size $10\log n$. ...
3
votes
0answers
76 views

Finding modular decomposition of graph

I am trying to learn how to find modular decomposition of graph using the method given in the paper Simpler Linear-Time Modular Decomposition via Recursive Factorizing Permutations. I am unable to ...
1
vote
0answers
56 views

Pruning a graph by removing vertices not part of any minimal Steiner tree

Given a sizable graph $G = (V, E)$, with $|V| \approx 1400$ vertices and $|E| \approx 1600$ edges, I have an optimization problem to find a connected subgraph of $G$ of size $k$ such that a given ...
6
votes
0answers
183 views

NP-hardness of tasks graph assignment to two heterogenous servers

I have a problem with determinig if the following assignment problem is NP-hard. Any comments and suggestions would be appreciated. Problem definition Given is a directed acyclic graph $G=(V,E)$ ...
1
vote
1answer
202 views

Is there simple reduction Dominating Set to Vertex Cover?

Is there simple reduction Dominating Set to Vertex Cover? In the other direction the reduction is simple. Searching the web returned blog. It warns This is not finished yet and experiments ...
0
votes
0answers
33 views

Estimating Graph/ Network Accuracy

If I'm creating a (social) network using some automatic system, which I know is not 100% accurate but for which I can estimate the rate of error, what, if anything, can I say about the accuracy of the ...
0
votes
1answer
71 views

What is a minimum vertex separator as in this definition?

In a research paper the following definition appears that I'm not able to understand completely. Let $G=(V,E)$ be an undirected unweighted graph with vertex set $V$ and edge set $E$, no self-loops, ...
1
vote
0answers
97 views

Complexity of an algorithm for deciding 3-colorability of graph by the chromatic polynomial modulo $x-3$

As explained on MO computing the chromatic polynomial $P(G,x)$ modulo $x-3$ is enough for deciding 3-colorability. For non adjacent vertices $u$ and $v$, $G+uv$ is the graph with the edge $uv$ added ...
0
votes
1answer
45 views

References to learn more about graph laplacian.

I have vaguely heard of this connection between random matrix theory and graphs (the spectral gap of their laplacians) on compact Riemann surfaces. Can someone give a pedagogic reference which ...
5
votes
0answers
66 views

Sparse subgraph preserving rooted edge connectivity up to $k$

For a graph $G=(V,E)$ with $n$ vertices and $m$ edges, a subgraph of $O(kn)$ edges is an $r$-rooted-$k$-sparsifier if it preserves the local edge connectivity from $r$ to every other vertex up to ...
2
votes
0answers
57 views

Weighted graph as average of many unweighted graphs

I have a measure $L(G)$ that is only valid for unweighted graphs because is based on discrete distributions and can't be extended to weighted graphs. My idea is that if I consider a weighted graph as ...
3
votes
2answers
270 views

How hard is a variant of graph automorphism problem?

I'm interested in a variant of graph automorphism problem (which is $NPI$ candidate). Restricted GA Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ pairs of nodes $(u, v)$ where $u ...
3
votes
1answer
81 views

any relation/ overlap between small world graphs, scale free graphs, and expander graphs?

small world graphs (eg Watts-Strogatz model & others) and scale free graphs are a relatively recently discovered graph type via mainly empirical analysis of large real-world graphs (eg via Big ...
3
votes
0answers
44 views

Interpolating the Tutte polynomial at the values of two hyperbolas

In a MO question basically I asked when the Tutte polynomial of planar graph can be uniquely determined by the polynomially computable values at the special points and at the two hyperbolas. The ...
4
votes
1answer
48 views

Bipartite scale-free networks

The Barabasi-Albert model describes a mechanism of generating random scale-free networks: Growth: Starting with a small number ($m_0$) of connected nodes, at every time step, we add a new node with ...
3
votes
0answers
40 views

Bipartite small-world networks

The Watts-Strogatz model describes a mechanism of generating small-world networks. The idea is to start from a ring network in which each node is connected a fixed number of its closest neighbors. ...
2
votes
0answers
43 views

Linear ordering of bipartite tournament graphs

I have an ordered bipartite graph such that every node of the first node set is connected to every node in the second node set by an edge of a given direction (i.e., a so-called bipartite tournament ...
0
votes
0answers
76 views

Regularlity lemma and exceptional set

Regularity lemma is one of the most basic tools in algorithmic thoery and pure math theory like additive number theory and combinatorics. This lemma is stated two ways: the existence of a partion ...
5
votes
0answers
95 views

Spectrum of absorbing random walk for regular graphs

I have a symmetric Markov chain given by the matrix $P$. Let $M$ be a set of special states of the chain (called marked states, they correspond to solutions to some problem). We can write $P$ as ...
15
votes
0answers
153 views

Mixing properties of random walks on graphs

I have a question about this paper (not behind a pay wall) on the Cheeger inequality for graphs. One of the main ideas of the paper is that random walks on graphs can be used to find sets with small ...
6
votes
0answers
96 views

Confusion about reduction counting vertex covers to counting cycle covers

This confuses me. One easy case of counting is when the decision problem is in $P$ and there are no solutions. A lecture show that the problem of counting the number of perfect matchings in a ...
9
votes
1answer
223 views

Hidden path in square grids

I stumbled on an open problem posed by David Eppstein and I am interested in its complexity status. He conjectured that it is NP-complete. Input: $n$ by $n$ matrix of 0’s and 1’s, sequence of $n^2$ ...
0
votes
1answer
160 views

Proving properties of Random Graphs

I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas. Consider the random graph model $G_{n,p}$ where its ...
2
votes
0answers
79 views

What is the name for this special case of the Travelling Salesman involving dynamic edge costs?

This is a modeling / taxonomy question. Is there a name for this type of problem? I came up with the following graph problem for a pizza delivery truck, which starts with zero dollars and enough fuel ...
2
votes
1answer
108 views

When replacing an edge with a graph gadget preserves graph isomorphism?

The transformation replacing an edge by a graph gadget is widely used in graph theory. As an example, in an answer Marzio De Biasi subdivided edges which increases the girth while preserving GI. A ...
-1
votes
1answer
99 views

What can we say about all cycles in graphs (connected undirected graph) [closed]

I am considering one optimization problem who is known to be NP hard in the general setting. But there is application of this problem on the cylces of graph. This problem involves several sets and ...
4
votes
0answers
110 views

Complexity of edge coloring graphs with $\Delta(G) \ge n/3$

Let $C$ be the class of graphs satisfying $\Delta(G) \ge n/3$, where $\Delta(G)$ is the maximum degree of a graph $G$, and $n$ denotes the number of vertices. What is the complexity of edge coloring ...
5
votes
1answer
150 views

The Overfull conjecture in graph theory and $coNP$

I am not good at complexity, but got a possible relation between a plausible conjecture in graph theory and $coNP$. Graph $G$ is Class 1 if it can be edge colored with $\Delta(G)$ colors, otherwise ...
2
votes
1answer
84 views

For which graph classes the fractional chromatic index rounded up equals the chromatic index?

Let $\chi'_f(G)$ be the fractional chromatic index. For which graph classes $\lceil \chi'_f(G) \rceil = \chi'(G)$? Since $\chi'_f(G)$ is computable in polynomial time, solving this gives tractable ...
6
votes
0answers
78 views

Hard extendability problems

In extendability problem, we are given part of the solution and we want to decide whether we can extend it to a complete solution. Some extendability problems are efficiently solvable while other ...
1
vote
0answers
37 views

Maximal Unit interval graph construction

Is it possible to construct a unit interval graph with $n$ vertices and clique number $k$ such that any other unit interval graph with same number of vertices and clique number is a sub-graph of that ...
0
votes
1answer
130 views

Does this paper imply graph isomorphism is polynomial for cubic and $4$-regular graphs?

This paper gives example of polynomial GI for certain graphs. Probably I am misunderstanding the paper, but appears to me it implies polynomial GI for cubic, $4$-regular and probably higher degree ...
7
votes
4answers
466 views

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Crossposted from MO. Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there NP-hard graph problems ...
4
votes
1answer
131 views

$\ell_1$ norm of Fourier coefficients vector for the hypercube

Let $G$ be the normzlied hypercube graph on $2^d$. It is a Cayley graph and it is well known that its eigenvalues are given by $\lambda_r = 1-2\frac{|r|}{d}$ for every $r \in \{0,1\}^d$. Given a ...
1
vote
0answers
40 views

Minimum Clique edge cover to cilque vertex cover

Suppose, there is an algorithm for enumerating minimum clique edge cover. Is it always possible to convert the algorithm to enumerate clique vertex cover ?
2
votes
1answer
53 views

Infinitary Counting Logics: 1-sorted vs. 2-sorted framework

There are two ways to extend infinitary logic with counting: Grädel's way (cf. p. 11): We extend $L_{\infty\omega}$ by introducing a counting existential quantifier: $$ \mathcal{A} \models ...
-4
votes
1answer
120 views

Destroy shortest path in graph

Given graph G(V,E)and two vertices A and B, show how to eliminate the least number of edges so that length of shortest path between A and B become longer.(I need an algorithm)