Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

1
vote
0answers
87 views

Tricky computations in graph theory proof

Let $0 < p < 1$ be a constant, and set $b = 1/p$. Let $0 < \epsilon < 1/2$. Given a natural number $r \ge 2$, let $n_r$ be the maximal natural number for which $\binom{n_r}{r} ...
1
vote
0answers
55 views

Bridge in a multigraph

According to Wikipedia, "a bridge in an undirected graph is an edge whose deletion increases the number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in ...
1
vote
0answers
126 views

General theory of graph coloring

In Ben Steven's article Colored graphs and their properties I read: We "color" a graph by assigning various colors to the vertices of that graph. [...] this process of coloring is generally ...
1
vote
0answers
46 views

How to sample the walk which visits each vertex of a graph specific number of times?

Is there any MCMC mathod that allow me to uniformly sample from all feasible walks where the following restrictions apply: ...
1
vote
0answers
139 views

Classifying graphs by patterns in their adjacency matrices

Given a set $S$, how can we classify different graphs $G(S)$ (tree, connected/disconnected, ...) based on the patterns of the 1's and 0's in their adjacency matrices $M(G(S))$?
1
vote
0answers
98 views

Bounding box for netwokx graph using matplotlib

I have tried to make a graph out of x,y co-ordinates from an area and display it using matplotlib but all the nodes sort of got overlapped as there is little difference between the when compared to ...
1
vote
0answers
51 views

An optimization involving (random) graphs

Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $-1$. Call this a configuration $\sigma \in \{+1,-1\}^n$. The number of $+1$s that we have to assign is ...
1
vote
0answers
137 views

Randomly Generating Connected Directed Acyclic Graphs

I'm looking for a way to generate random connected directed acyclic graphs, where I can specify the number of vertices that have no outgoing edges (leaf vertices). Anyone ever seen such a thing, or ...
1
vote
0answers
437 views

the number of shortest path between two points

I know that visibility graph is used to determine the shortest path between two points a mong a set of obstacles in the plane. So in the case that obstacles are triangles, is the maximal number of ...
1
vote
0answers
111 views

Shortest path variation

I'm looking for a solution to the following problem, related to shortest path. You are given a directed Graph $G = (V,E)$, source $s$, targets $t_1, t_2, \cdots , t_k$ and costs $c_{ij}$ for ...
1
vote
0answers
71 views

Increasing size of graph with respect to time

A graph $G(V,E)$ is growing with following rule: At every time step $t$, $An_t$ nodes are added to the graph. When choosing the node to which the new node connects to, we assume that the probability ...
1
vote
0answers
56 views

“Optimaly” reordering the vertices of a hypergraph.

I am not even sure of how to search for an answer to this, or how to approach the problem myself, so I thought I would try to ask it here. Consider an n-vertex hypergraph where the vertices are ...
1
vote
0answers
143 views

Estimation for ramsey number $R(3,k)$.

Previously I have shown that for any positive integers $k,l$, and any real number $p\in (0,1)$, ramsey number $R(l,k) \geq n- {n\choose k} p^{{k \choose 2}} - {n\choose l} (1-p)^{{l \choose 2}}$. Now ...
1
vote
0answers
202 views

A tree that does not satisfy: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$?

It is a strange question on a book. Give an example of a tree $T$ that does not satisfy the following property: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$. I ...
1
vote
0answers
982 views

Dijkstra's Algorithm on a Directed Graph with Negative Edges Only Leaving the Source

I've been trying to figure out if Dijkstra's algorithm will always succeed on a directed graph that can have edges with negative weights leaving the source vertex only (all other edges are positive), ...
1
vote
0answers
53 views

Adding metric to matroids in order to describe graphs whose vertices are points in Euclidean space

My concern is about finding a mathematical model in order to describe graphs as combinatorial structures (with operations like edge addition, deletion and so on), and as elements in the Euclidean ...
1
vote
0answers
61 views

A non-distinct system of representative edges.

I have the following problem: Let $ \mathcal{G} = \{ G_i \}_{i=1 \ldots n} $ be a collection of graphs. I would like to find a "system of representative edges" $ f : \mathcal{G} \rightarrow \bigcup_i ...
1
vote
0answers
57 views

Any interesting conditions on a graph with the following properties?

This is quite a soft question. I'm looking for any properties that a graph $G$ on $n$ vertices satisfying the following conditions might have: $\chi(G)=n-2$ $|E(G)|>(n^2-3n+6)/2$ Clearly, for ...
1
vote
0answers
51 views

Complexity of integer assignment to hypercube vertices?

I came across this problem whilst studying Gray codes during some current optimisation work. It seems likely to me that the complexity of it may be known. However, my background is not in computer ...
1
vote
0answers
80 views

determine the max flow function $f^*$ in a network given the maximum flow value

Suppose I have a Network N ( i.e. just a Digraph D(A,V) with A=Arcs, V=Vertices; combined with a capacity function $c:V x V \to \mathbb{N}\cup\{0\}$ and two vertices s:=source, t:=sink singled out) ...
1
vote
0answers
133 views

Spielman. Spectral Graph Theory Proposition

Spielman says in Lecture 3: Laplacians and Adjacency Matrices Fiedler’s Theorem will follow from an analysis of the eigenvalues of tri-diagonal matrices with zero row-sums. These may be viewed as ...
1
vote
0answers
132 views

'Rank' in a hypergraph

I'm teaching myself about hypergraphs and can't get my head around a statement in the book I'm using which seems just plain wrong. Hopefully someone here can explain why either I'm misunderstanding ...
1
vote
0answers
219 views

Finding the number of spanning trees of a given height

I hope I can avoid being confusing, but here goes. I have a graph $(V, E)$, connected, undirected and with no loops. I also have an assignment of integer-valued weight to each edge of the graph. ...
1
vote
0answers
64 views

Graph classes equivalent to circular-arc graph

I'm looking for properties of circular-arc graphs, mainly its equivalence relations with more common graph classes. Simular to properties such as $\mathit{interval} \equiv \mathit{chordal} \cap ...
1
vote
0answers
136 views

Not an interval graph, so what is it?

I've constructed a graph in a simular way an interval graph would be constructed from the overlap of intervals. But my intervals are from a modular domain. Given $\mathit{interval} \equiv ...
1
vote
0answers
300 views

Augmenting Path Algorithm for Maximum Matching

I have a rather cryptic pseudo code version of the augmenting path algorithm for finding a maximum matching in a bipartite graph in my notes. I m not sure it s correct, and there are some parts that ...
1
vote
0answers
76 views

Order the nodes of a directed graph

Given a directed graph $G$ and a number $k$, how can I order the nodes (let's say in an array) so that the distance between each two connected nodes is less than or equal to $k$?
1
vote
0answers
540 views

Finding maximal set of vertex disjoint augmenting paths in Hopcroft Karp

In trying to implement the Hopcroft-Karp algorithm I have run into something I do not quite understand. In the step where you find the maximal set of vertex disjoint augmenting paths. How does one ...
1
vote
0answers
92 views

Concerning The 'Price-Collecting Steiner Tree'

I'm a Master student at the University of Leuven, Belgium. I have to make a report of a case concerning the 'Price-Collecting Steiner Tree'. We have our model and our restrictions. We are just looking ...
1
vote
0answers
2k views

Dijkstra algorithm failures on negative weighted nondirected graphs

I am studying for an oncoming test from graph theory and I've been solving some problems from homework assignments few years old. So I unfortunately can't find the solutions anywhere. Therefore I ...
1
vote
0answers
102 views

Graphs: the best path

Assume we have a path in an undirected cyclic weighted graph. Assuming we have an engine that can find a path from node A to node B in such a graph, is there an easy way/algorithm to figure out if the ...
1
vote
0answers
91 views

Ordered-pair graphs

Consider a (finite) set $S$ and the digraph $G$ with vertex set $V(G) = S^2$, i.e. the ordered pairs over $S$. Let there be an arrow from $(v,w)$ to $(x,y)$ iff $v = y$. How can these "ordered pair ...
1
vote
0answers
221 views

Special properties of connected hypergraphs with fewer edges than vertices?

Consider a connected graph G which has n vertices and m edges. If m = n − 1, then we know immediately that G is a tree; which is notable because it has no cycles — ...
1
vote
0answers
158 views

Shortest path length prediction

Is it possible to predict the edges of the shortest path (or number of walks) having data such as density, average degree of nodes, degree of each node, number of nodes and number of edges? or do I ...
1
vote
0answers
499 views

Action of group on graph

In the study of groups acting on graphs, one often starts with hypothesis "Let $X$ be a graph, and $Aut(X)$ acting on $X$ without inversion.." But, is it true that $Aut(X)$ always acts on $X$ without ...
1
vote
0answers
87 views

Find a special type of subgraph of certain edges that minimizes the cost of the edges in that subgraph

Say we have a graph $G=(V,E)$. Each edge $e$ in $E$ has a cost $c > 0$. Now we want to find a subgraph $G'=(V',E')$ of $G$ such that there is at least $k$ edges, $k>0$, and ...
1
vote
0answers
207 views

Strongly-Connected Components's Graph by running DFS

I got this question, and I'd be happy for help. G=(V,E). $G_S$ is a Strongly-Connected Components's Graph. I need to prove, that if there is only one Component ($C_0$) which is not with incoming ...
1
vote
0answers
162 views

l1-metric and cut metric equivalence

I would like to show that the following two statements are equivalent. Let (A, d) be an n-point metric space. And B set of $\binom{n}{2}$ pairs of points of A. $\exists t \geq 1$, integer m, and ...
1
vote
0answers
244 views

Cycle Basis = Matroids? How is it even possible?

Can anyone explain to me why a cycle basis hones the properties of a matroid? Especially points 2 & 3. How can a subset of I also be a member of I? Isn't a cycle basis supposed to be consisted of ...
1
vote
0answers
281 views

Partition of graph into independent sets of consecutive vertices

Sorry for my English. Here is the question: $G=(v,e)$, undirected graph, $V=\{v_1,v_2,\ldots,v_n\}$. the vertices are organized in sequence from the smaller one to the biggest $v_1,\ldots,v_n$. We ...
1
vote
0answers
267 views

Average distance between features in plane of connected points with known average distance

I was doing some thought experiments for a game project, and while considering something related to pathfinding, this problem came into my head. Say we have an infinite plane that is covered with an ...
1
vote
0answers
252 views

Sample algorithm to “linearize” a graph

Simplifying a business example, I have the following situation: Some objects should be distributed in a graph in most "linear" way possible for a given "thermometer". Say, a voyager visits some ...
1
vote
0answers
440 views

Does this solve the zero sum subset problem?

Let $G$ be a directed graph which contains $N$ vertices, and which satisfies the following condition: each vertex of $G$ has at least one incoming edge. (For clarity, a vertex $V_1$ has an "incoming ...
0
votes
0answers
9 views

isoperimetric inequalities in permutohedron

Consider the graph whose vertices are all n! permutations of numbers 1..n and there is an edge between two vertices iff we can get from one to another by an adjacent transposition. We call this graph ...
0
votes
0answers
21 views

unique cycles in strongly connected labeled digraphs.

Define a "characterizing cycle" as a cycle in a labeled digraph, along with a distinguished node, such that the sequence of labels starting from that node is unique to that cycle and node. Note: the ...
0
votes
0answers
33 views

Nullifying columns of a matrix by nullifying rows

Let $A$ be a real rectangular matrix. Each column of $A$ is a nonzero vector. Now each row of $A$ is nullified with probability $p$, all independently of each other. What is the probability that ...
0
votes
0answers
41 views

Number of ways to connect N nodes with K edges.

Given a graph with N nodes, I have to find the number of different ways the nodes can be connected with the K edges such as the resulting graph is connected. For N = 3 and K = 2, the possibilities ...
0
votes
0answers
15 views

Semi-complete partites

Is there a name for regular bipartite graphs where each partite has the semi-completeness property (that is, for each two vertices $i$,$v$ in the partite $V$, there is a path $\{i,w,v\}$, where $w$ ...
0
votes
0answers
24 views

Find mean value of amount of Hamiltonian cycles in the random complete directed graph

We are given the random tournament (randomized uniformly) on $n$ vertices. Task is to find the average value of the amount of Hamilton cycles on that tournament. This problem was covered in the ...
0
votes
0answers
29 views

Why is it not possible to draw the $\overline{Q_3}$ in the plane

I am trying to prove that $\overline{Q_3}$ is nonplanar. I know that $Q_3$ is planar and I have attempted to use the corollaries derived from Euler's planarity Theorem to show it is nonplanar but it ...