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
1answer
144 views

Max flow in a flow network such that $e \in E$ has the maximum flow it can have.

Given a flow network $G=(V,E)$, source $s$ , sink $t$ and capacity function $c:E \to \mathbb{R}^+ \cup \{0\}$ ; as well an edge $e=(u,v) \in E$. I need to find an efficient algorithm which finds among ...
1
vote
2answers
216 views

Tournament Algorithm for Quartets

I'm currently trying to find an algorithm to place players during a Mahjong tournament. Here are the requirements : Number of players in the tournament : $n$ with $n \equiv 0 \pmod 4$ Number of ...
1
vote
1answer
110 views

Finding sphere-like topologies in a nonplanar granular graph (help with problem definition)

Update/clarification: I'm looking for an elegant problem definition, not necessarily a solution, so please feel free to answer in that vein. (also check the end for additional clarifications) NOTE: I ...
1
vote
1answer
121 views

What is the average distance of a combination set?

I'm working on a genetic algorithm and would like to map each function to a set of "codons". So + -> 011. Given this, I would like to figure out how easy it would be for any given codon set to mutate ...
1
vote
3answers
604 views

Measure the connection between two nodes in a graph

This is a question about complex networks We have various ways to measure the centrality or importance of a node. $$\textrm{importance} :: \textrm{node} \rightarrow \mathbb{R}$$ The simplest such ...
1
vote
1answer
161 views

Vertex Cover - upper bound

A few definitions: $\mathsf{VC} = \{ (G,k) \mid \text{There exists a vertex cover of size $k$ in $G$}\}$ $\mathsf{VC_{LOG}} = \{ G \mid \text{There exists a vertex cover of size $\leq \log |V|$ in ...
1
vote
1answer
203 views

Probability of vertices in a complete bipartite graph being disconnected such that no path of length 2 remains between them?

My problem is the following. I have a set of vertices $N$ and a set of vertices $H$. Each vertex $n \in N$ is connected by means of an edge to each vertex $h \in H$. So the two sets of vertices and ...
1
vote
1answer
163 views

Sum in tree nodes - algorithm

I've got one very hard problem. Given a tree with nodes with integers. We need to find the largest sum of label values for a set of nodes which does not include any adjacent pair of nodes. ...
1
vote
1answer
2k views

Getting the shortest paths for chess pieces on n*m board

I originally posted this question of stackoverflow but I was suggested to post it here. So: I am stuck solving a task requiring me to calculate the minimal number of steps required to go from point A ...
1
vote
1answer
154 views

How does graph theory describe a sequence or line or path of nodes?

I have a dataset of pairs of map coordinates, and I suspect that they could be connected to make a path. However, I'm not sure what the end points are, or if the coordinates actually make a path. ...
1
vote
1answer
57 views

Infinite families of Moore graphs

Is there another infinite family of Moore graphs besides the sequence of cycle graphs $C_{2d+1}$? (By definition a Moore graph must contain a cycle of length $2d+1$ where $d$ is its diameter, so ...
1
vote
1answer
91 views

“Random Cartesian Product” of graphs

If $G= (V(G), E(G))$ and $H=(V(H), E(H))$ are graphs. Consider the set $\mathfrak{R}(G,H)$ of "Random Cartesian Product" whose member are graphs $K =(V(K), E(K))$ defined as follow: $$V(K) = V(G) ...
1
vote
1answer
161 views

What is the relationship between shortest path and density for undirected graph?

Does the shortest path increase or decrease with graph density in undirected graphs? Or is there no clear relationship?
1
vote
2answers
107 views

Need help to prove that If $G$ is 2 - self centered graph. then how to prove that $G$ has at least $2n - 5$ edges, where $n\geq 5$.

If $G$ is 2 - self centered graph. then how to prove that $G$ has at least $2n - 5$ edges? where $n\geq 5$. I started by assuming if number of edges $\mid E\mid\leq 2n-6$ then there exist a vertex ...
1
vote
1answer
127 views

How to apply the Poincaré formula to a regular n-gon?

I've been trying to solve the following home task: Choose $n$ points ($n\ge 2$) on the circle's circumference and connect them all with each other using chords. In result, the circle is ...
1
vote
1answer
634 views

Proving properties of a simple undirected graph

Given a connected simple undirected Graph (V,E), in which deg(v) is even for all v in V, I am to prove that for all e in E (V,E\{e}) is a connected graph. ...
1
vote
1answer
233 views

Reference: Compendium of interesting graphs

I've been writing a little about some results on graph theory, and I want some nice examples of applying the results to some interesting finite connected graphs to show how the results might be ...
1
vote
1answer
100 views

Prove the following inequality: $N(P,P,2)\leq 4^{P-1}$

I've made very little headway on this problem, so any help is appreciated. Edit: Sorry, I should have explained that. In general, $N(p,q,2)$ is the smallest value of $n$ such that a red-blue ...
1
vote
1answer
43 views

Characterizations of operation that take a path and produce a star in a tree

I was looking at this operation in a tree, and try to relate it to the diameter of the tree. Pick a path of length $m$, so let it be $v_1v_2\ldots v_mv_{m+1}$. Remove all the edges in the path, and ...
1
vote
1answer
160 views

Question on the number of directed edges in a tournament.

I want to show that there exists $c>0$ constant s.t for any tournament on $n$ vertices there are two disjoint subsets A and B s.t: $$ e(A,B)-e(B,A) \geq c n^{\frac{3}{2}}$$ I know of the theorem ...
1
vote
1answer
494 views

Finding planar representation of graph

If it is known that a graph is planar, how do we find a planar representation of the graph? Is there any method other than trial and error? Thanks a lot.
1
vote
1answer
41 views

Getting the formula of a live counter

I'm looking to replicate this greenhouse gases counter in my website. Poking around i found the initial data for the formula. The counter use the following information: Beginnig date: 2012/03/01 ...
1
vote
3answers
104 views

Matchings Containing Given Edges

Version 1 Is there a connected graph containing edges $e_1, e_2, e_3$ such that there is a perfect matching containing any two of the edges but no perfect matching containing all three? EDIT: ...
1
vote
1answer
487 views

Transitive reduction: calculating “relation composition” of matrices?

I have graphs represented by matrices. For example, $\begin{matrix} 0&0&0\\1&0&0\\1&1&0\end{matrix}$ Produces this graph: The graphs are supposed to be transitive, i.e. ...
1
vote
1answer
1k views

Connectivity in Graphs: removing edges vs. removing vertices

For a simple undirected connected Graph $G(V,E)$ I say the edge $xy \in E(G)$ disconnects G if the resulting graph G' does not have a path from every vertex to every other vertex. Now suppose I have ...
1
vote
1answer
451 views

Bipartite graph non-isomorphic to a subgraph of any k-cube

Find a bipartite graph that is not isomorphic to a subgraph of any k-cube
1
vote
1answer
176 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
1answer
95 views

To encode the shape of an ordered tree into bit sequence more efficiently

Suppose we want to save the shape of an ordered tree of n node, each node has maximal 2 children. If it is a binary tree, we must use 2n bits. Since in our situation, we don't have left or right ...
1
vote
1answer
498 views

Number of possible Prüfer codes

I am trying to solve the following problem in my book: (Code stands for Prüfer code) Consider labelled trivalent rooted trees $T$ with $2n$ vertices, counting the root labeled $2n$. The labels are ...
1
vote
1answer
160 views

Graph, planar or not?

A graph $L_n$ has vertices $V=\{l_1,l_2,\dotsc,l_n\}\cup\{r_1,r_2,\dotsc,r_n\}$ and edges $E=\{(l_i,r_j): i \ge j\}$ . Which of these graphs $L_1$, $L_2$, etc. are planar and which are not? For ...
1
vote
1answer
417 views

Min. number of vertices in graph as function of $\kappa(G)$ and $\operatorname{diam}(G)$

Question I found in "Introduction to Graph Theory" by Douglas B. West: Let $G$ graph on $n$ vertices with connectivity $\kappa(G)=k \geq 1$. Prove that $$n \geq k(\operatorname{diam}(G)-1)+2$$ ...
1
vote
1answer
142 views

Vertex coloring

Disclaimer: I'm not a mathematican. Please answer in a way a non-mathematican can understand. Thank you. I'm building kind of a wooden puzzle and got stuck. My problem is: I have squares whose 4 ...
1
vote
1answer
110 views

counting edges in tesselations of a torus

Tesselate a torus with finitely many simply connected polygons. Do not allow four or more of them to meet at a point. In counting the edges, don't count a "straight line" as just one edge if it's ...
1
vote
1answer
243 views

Comparing the number of cuts and paths in graph

How would you prove that the number of cuts in a graph (where cut is a set of edges which split two vertices) cannot be smaller than the number of directed paths from one vertex to the other?
1
vote
1answer
1k views

Simple graphs (edges, nodes etc.)

Draw all possible graphs that can be constructed from the vertices $V_1=\{a,b,c\}$. Answer: Pic: I believe this is all of them (bottom three are all the same). How many such graphs have no edges? ...
1
vote
1answer
210 views

Graph and matching of size

Let $G$ be a graph with $p$ vertices, with minimum degree $d$. Suppose $d \leq p/2$. Prove that $G$ has a matching of size at least $d$. Any advice on how to approach this question? I'm trying ...
1
vote
1answer
376 views

Finding the Augmenting Path

I had a question about a specific graph, (a) found here: http://upload.wikimedia.org/wikipedia/commons/9/98/Maximum-matching-labels.svg If I were to add an edge between the two leaves of the tree, ...
1
vote
1answer
61 views

A lower bound on the number of edges in a graph satisfying a “subset matching” property

Given a graph on $n$ vertices, I wish to find a lower bound on the number of edges required before the graph can has the following property: Every subset of 4 vertices contains a matching. Put more ...
1
vote
1answer
137 views

walks on proper coloring of odd cycles: comparing asymptotics

Let $C_n$ be an odd (undirected) cycle with $n$ vertices. Let $f$ be the proper 3-coloring of $C_n$ where one vertex is colored $2$ and we alternate $01$ otherwise (0101...012 coloring). Let $g$ ...
1
vote
1answer
114 views

Partitioning a graph with degrees at most 3

We define a partition of an undirected graph $G=(V, E)$ as some set $A \subseteq V$, which partitions $V$ into $A$ and $V \setminus A = B$. Define $n=|V|$. We call a partition $\alpha$-balanced if ...
1
vote
1answer
2k views

shortest path between two vertices in a graph

I realize this is a very basic question, but I am amazed that I didn't find much useful information on the web: Given a (directed/undirected) edge weighted graph G, and two of its vertices u,v, is ...
1
vote
1answer
803 views

Vertex Cover Proof

I am working on an exercise describe like so: Without using knowledge about cliques, prove that a graph G has an independent set of size k if and only if G has a vertex cover of size n - k where n is ...
1
vote
2answers
627 views

Prove König's theorem using Dilworth's theorem

I am trying to derive König's theorem from Dilworth's theorem, but it seems like I'm stuck. I know that I have to define some kind of binary relation on the set of a bipartite graph's vertices, then ...
1
vote
1answer
483 views

What is a “mixed graph”?

I'm working on a digraph problem in which bidirectional edges need to be treated separately. As such, we could consider them as undirected edges. Clearly, if I replace bidirectional edges with ...
1
vote
1answer
117 views

What is the structure of this object? (Profinite trees)

Let $T_n$ be the binary rooted tree of $n$ levels. Let $$ \phi_n : T_{n+1} \rightarrow T_n$$ be the quotient map collapsing level $n+1$. What kind of structure does the inverse limit have?
1
vote
3answers
107 views

Should one think of a network as a connected graph ? (Or: What is the right way to think of a network?)

In the definition of a network, are we only considering connected graphs ? Because I keep encountering definitions that don't assume explicitly that we deal with connected graphs, but which would be ...
1
vote
1answer
33 views

Scaling a range of values without a known maximum

I want to know is it possible to scale a set of numbers without knowning the upper limit. Say for example I have 1000 number values. I want to plot each of these values within a range of 0- 90. Is ...
1
vote
2answers
2k views

Bellman-Ford algorithm: why V-1 number of relaxation iterations?

Why does Bellman-Ford algorithm perform V-1 number of relaxation iterations? I feel that it is correct when going through examples. But how do we explain it for the general case? I have gone through ...
1
vote
1answer
192 views

Term for a fully connected balanced graph (Rock paper scissor)

Is there a mathematical, graph theory, game theory term for a graph that is fully connected and balanced evenly with each other node. I'm thinking in situations like Rock paper scissors where each ...
1
vote
1answer
282 views

Showing that a particular graph is Hamiltonian

I am trying to prove the following: Let $Q:=\{1,2,\cdots q\}$. Let $G$ be a graph with the elements of $Q^n$ as vertices and an edge between $(a_1,a_2,\cdots a_n)$ and $(b_1,b_2,\cdots b_n)$ if and ...