Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.

learn more… | top users | synonyms

0
votes
1answer
33 views

Recognizing interval graphs--“equivalent intervals”

I was reading a paper for recognizing interval graphs. Here is an excerpt from the paper: Each interval graph has a corresponding interval model in which two intervals overlap if and only if ...
1
vote
1answer
35 views

Category theory and graphs

Could most categories , or a finite part of them be represented on a subset of a complete graph of N vertices (Kn) which is connected. and partly directed? Could all the axioms of category theory be ...
1
vote
1answer
14 views

The min cut capacity in a network based on a bipartite graph (Hall's Theorem)

Thanks to Yuval Filmus, I got to read these lecture notes by Trevisan. At the bottom half of Page 5, The capacity of cut $S$ is the number of edges that go from $S$ to $\overline{S}$, that is ...
0
votes
0answers
19 views

Is the vertex cover problem NP-Hard in general graphs and in P for bipartite graphs? [on hold]

Wikipedia says that finding the minimum vertex cover is NP-Hard. However, for bipartite graphs, I can solve the maximum matching problem with Hopcroft-Karp in polytime and then, through Koenigs ...
1
vote
1answer
51 views

Shortest directed path connecting given subset of vertices

Given weighted directed graph $G = (V,E,w)$, where $w : E \to \mathbb R^+$ source vertex $v \in V$ vertex subset $U \subset V$ how to find a shortest directed path from $v$ containing all vertices ...
2
votes
2answers
94 views

What is the difference between maximal flow and maximum flow?

What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a ...
2
votes
1answer
46 views

n-Cube as a Cayley Graph

I'm taking a class on graph theory that uses "Graph Theory (Graduate Texts in Mathematics)" by Bondy and Murty. One of the questions is about Cayley graphs and the n-cube, and I don't understand how ...
0
votes
1answer
27 views

Minimizing the following objective function with matrices

I am trying to work out centrality in a network using Freeman's network centrality. I have an in degree of 83 and an out degree of 110. I want to work out the network centrality using my out degree ...
-1
votes
0answers
29 views

Height of H-Tree [closed]

I studied VLSI layout design and in that they discussed the most efficient way to layout is using an H-Tree as the area occupied is smallest compared to for example a binary tree. Can anyone ...
-1
votes
2answers
48 views

number of edges in a graph

I got a problem related to graph theory - Consider an undirected graph ܩ where self-loops are not allowed. The vertex set of G is {(i,j):1<=i,j <=12}. There is an edge between (a, b) and (c, ...
1
vote
1answer
37 views

Understanding sparse graphs

Im looking online for a good definition of sparse graphs, but i'm confused. Is a sparse graph effectively a big one, with millions/billions of nodes. An example, is a real world one - like Facebook. ...
3
votes
1answer
37 views

What is the common terminology to refer to the nth ancestor of a tree root?

Reading the Wikipedia article for common terminology for tree (data structure) there are several near references, but I don't read a formal declaration for how to refer to a specific generation of a ...
5
votes
2answers
47 views

Number of descendants of each node in a DAG

1) Is there a better algorithm than the naive O(|E|.|V|) to compute the number of descendants of each vertex in a DAG? 2) Is there an online algorithm to do so, assuming that nodes are added one by ...
5
votes
1answer
256 views

Why is the complexity of negative-cycle-cancelling $O(V²AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
1
vote
1answer
36 views

Edges in and out of cycles and their relation to connectivity of the graph

We know that if an edge is a part of a cycle in an undirected connected graph $G$, then if we remove that edge the graph is still connected. Is the opposite true? If an edge is not a part of a cycle ...
0
votes
1answer
155 views

find the minimum number of vertices in a directed graph from which the other vertices are reachable

In a directed graph i want to call bfs on some of the vertices so that all of the vertices will be met. (in other words all of the other vertices are reachable from these chosen vertices.) I want to ...
2
votes
2answers
39 views

Reconstruct directed graph from list of ancestors for each node

I have a problem that I encountered that boils down to the following: Considered this directed graph I found on Google: I have the following information available to me ...
5
votes
0answers
35 views

Union of 2 expander graphs [closed]

Suppose that $G$ and $H$ are both expander graphs on the same node set with a second largest eigenvalue of $\lambda_G$ resp. $\lambda_H$. What can be said about the expansion of graph $G \cup H$? In ...
4
votes
1answer
106 views

What is average number of cycles in an undirected ordered graph of size n?

What is average number of cycles in an undirected ordered graph of size $n$? I've tried finding out sum of number of cycles in all sorts of a graph of size n but I couldn't find that out.
3
votes
3answers
82 views

Difference between diameter of a graph vs longest path of the graph

I am curious what is the difference between diameter of a graph vs longest path of a graph. I just read diameter of a graph can be solved using Floyd warshall in O(V^3) while longest path can be ...
7
votes
1answer
214 views

Find which vertices to delete from graph to get smallest largest component

Given a graph $G = (V, E)$, find $k$ vertices $\{v^*_1,\dots,v^*_k\}$, which removal would result in a graph with smallest largest component. I assume for large $n = |V|$ and large $k$ the problem ...
5
votes
4answers
246 views

Approximating NP-complete problems

Say that for a particular problem, e.g., the independent set problem, it has been shown that no polynomial-time algorithm exists to solve it. Could we get around this by finding an algorithm which ...
0
votes
1answer
37 views

Show that this algorithm does not work for determining convex polygons

Context Consider this algorithm. If the set $\{\angle p_ip_{i+1}p_{i+2} : i=0,...,n-1\}$ does not contain left and right turns, output "yes the polygon is convex"; otherwise, "no". My answer ...
1
vote
0answers
28 views

Question about spanning trees and creating them through BFS and/or DFS algorithms

The question is as follows: True or False: For every non-directed connected non-weighted graph and for every spanning tree T of the graph there exists a vertex v such that T is a DFS tree with the ...
1
vote
1answer
92 views

Clarification sought for definition of a cut that respects a set A of edges in Graph Theory

From CLRS (3rd edition), I came have this question on page 626: Given these definitions from the text, DEFINITIONS: Given an undirected graph G = (V,E), 1. A CUT (S ,V-S) of G is a partition of V, ...
4
votes
1answer
52 views

Complexity of calculating independence number of a hypergraph

Let $G$ be a "hypergraph", a collection of vertices $V=\{v_1,v_2,\ldots,v_n\}$ and a collection of "hyperedges" $E=\{e_1,e_2,\ldots,e_m\}$, where $e_i\subseteq V$ and unlike normal edges, an edge may ...
1
vote
2answers
149 views

Undirected graph with 12 edges and 6 vertices [closed]

For school we have to make an assignment, and part of the assignment is this question: Describe an unidrected graph that has 12 edges and at least 6 vertices. 6 of the vertices have to have ...
1
vote
2answers
83 views

Spanning Tree - Equivalent Properties

I am working on the following problem: Suppose that $T$ is a spanning tree of a graph $G$, with an edge cost function $c$. Let $T$ have the cycle property if for any edge $e' \not \in T, c(e') ...
1
vote
1answer
58 views

Generalized Geography with repetitions

Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes. Last player to ...
2
votes
0answers
11 views

Generalized Geography with repetitions [duplicate]

Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes. Last player to move ...
0
votes
1answer
86 views

Find largest chromatic number of a full binary tree [closed]

This is a Discrete Math/Combinatorics Question from my hw…but I don't really understand the question. Find largest chromatic number of a full binary tree given the following depths: (Check all ...
2
votes
2answers
64 views

Application of Four color theorem

I was reading up on Four color theorem and am wondering if there is any practical application of it .( I dont think seperating the map into four different colors can be considered an application) I ...
1
vote
2answers
83 views

Calculate number of ways to color matrix using inclusion-exclusion principle

This was asked in a recent contest. The question asked to count the number of ways to color an $M \times N$ matrix with $K$ colours such that no two adjacent cells (sharing an edge) have the same ...
5
votes
3answers
131 views

Minimal spanning tree with degree constraint

I have to solve this problem: We have weighted $n$-node undirected graph $G = (V,E)$ and a positive integer $k$. We can reach all vertices from vertex 1 (the root). We need to find the weight of ...
0
votes
1answer
79 views

Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?

I am reading Prim's MST for the first time and wanted to implement the fast version of it . $m$ - The number of edges in the graph $n$ - The number of vertices in the graph Here's the algorithm ...
1
vote
0answers
80 views

Algorithm to determine a minimal cost graph [closed]

I'm trying to solve this problem: Given a collection of cities and the number of commuters between cities, design a network of roads for minimal cost where cost includes the cost of building the ...
2
votes
1answer
56 views

Similarity between two geometric shapes

I have two shapes in a 2D space, not necessarily convex, and I'd like to compare how similar they are. How can I define a robust distance metric to measure their similarity, and how can I compute it? ...
4
votes
2answers
496 views

Min cost max flow in bipartite run time

I have a bipartite graph with $|E|=O(|V|^2)$, a super-source and a super-sink. I am looking for the min-cost max-flow (the max-flow of all possible max-flows that has the minimum cost). For the sake ...
1
vote
1answer
19 views

On Shannon Capacity

Let $G$ be a graph whose Shannon Capacity is $\Theta(G)$. Is there any graph product for which the Shannon Capacity is $\Theta(G)^k$ where $k$ is the number of times the product is taken?
3
votes
3answers
208 views

Characterisation of graphs that are not 3-colorable

We know that all graphs with odd cycles (odd number of vertices) are not 2-colorable. Is there a similar characterisation for 3-colorability? I am looking for undirected graphs that are not ...
3
votes
1answer
46 views

Subgraph Isomophism Problem - Color Coding Technique - Proof Sketch

I am reading the paper Color Coding by Alon, Yuster, and Zwick. They state a theorem (6.3) that says if $H$ is a graph on $k$ vertices with treewidth $t$ and $G = (V, E)$, then a subgraph of $G$ ...
2
votes
0answers
27 views

Steiner tree wiring problem

I’m trying to find an algorithm that can give me an approximate solution for a wiring problem that I have been asked to look at. I believe this is closely related to finding a node weighted Steiner ...
3
votes
3answers
95 views

How to implement graph search to solve Sudoku puzzle

My teacher pointed out to us during lectures that we could use Graph Search to help us solve Sudoku puzzles which has left me puzzled . I dont see how this is possible as Graph Search is mostly ...
3
votes
0answers
33 views

Maximum Weight Independent Set in Circular-Arc Graphs (Proof of A Lemma)

I am reading the paper: "Maximum Weight Independent Set Of Circular-Arc Graphs and It's Applications" (http://link.springer.com/article/10.1007%2FBF02832044). And I had a question regarding the proof ...
-1
votes
2answers
83 views

Edge traversals of trees [closed]

I want to find a minimal vertex in a tree from which we can traverse some edges exactly twice then come back to that vertex then do it with the rest of edges. By minimal, I mean that the difference of ...
0
votes
1answer
43 views

Relation between digraph and NP-Complete problem

Can there be any relations regarding the number of nodes available in a digraph so that to qualify it as NP-Complete problem. If we consider this problem for instance: Input: A digraph $G=(V,E)$ and ...
7
votes
1answer
64 views

Number of edges required to guarantee $K_3$ as subgraph

I am trying to solve a given problem: Find an algorithm to determine if a graph has a clique of size 3 in $O(n^{2.81})$ steps. The hint given is that $2.81 > \log 7$. In order to solve this I came ...
5
votes
3answers
150 views

Maximum number of matched vertexes in a one-to-many bipartite graph

I have a variant of bidding problem at hand. There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who ...
2
votes
1answer
23 views

Meyniel's theorem + finding a Hamiltonian path for a specific graph family

Let's say we have a directed graph $G = (V, E)$ for which $(v, w) \in E$ and/or $(w,v) \in E$ holds true for all $v, w \in V$. My feeling is that this graph most definitely is Hamiltonian, and I want ...
0
votes
1answer
46 views

In Probabilistic Graphical Models, are Cliques and Clusters the same?

I am learning Probabilistic Graphical Models with the help of the videos on Coursera. I am in week 4 and I see cliques being mentioned often. But the graphs being discussed are cluster graphs. So are ...