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

0
votes
1answer
338 views

Network flow: Why is min-cut determined by unsaturated edges?

Suppose we have an oriented graph and max-flow has been determined. I found that to determine min-cut or minimum s-t cut can then be found by labeling graph nodes such that nodes belonging to source ...
0
votes
1answer
214 views

A problem on the friends and strangers theorem

There is a group of 20 people. Each pair of people are either friends or strangers, and each person finds exactly 6 strangers in the group. If all possible committees of 3 are formed from the group, ...
3
votes
2answers
325 views

Removing degree-2 vertices from a graph

Consider a map of a river system. Each point on the river line is a graph vertex. Some points have degree 1, at the start and end of a river, some have degree > 2 where rivers merge (or more rarely, ...
4
votes
1answer
167 views

Eigenvalues of a special block matrix associated with strongly connected graph

Definition Let $G=(V,E,A)$ be a strongly connected directed graph, where $V=\{1,2,...,n\}$ denotes the vertex set, $E$ is the edge set, and $A$ is the associated adjacent matrix with $0-1$ weighting, ...
3
votes
1answer
723 views

Finding the virtual center of a cloud of points.

Given: (latitude, longitude) points $P_1, P_2,\ldots, P_n$. Presumably, all the points should form a dense cloud. However, noise is possible. Needed: The virtual center of the points. For ...
0
votes
2answers
493 views

graph theory and forests

We were given an this question in my class: Prove that a forest with n vertices and m components has n-m edges using induction on m. Induction is not my strongest point and I was wondering if anyone ...
4
votes
0answers
321 views

Combinatorial problem on subgraphs of the Johnson graph

The following problem emerged from my project about distributed computing. First some definitions: Let $1\leqslant m \leqslant n$, $N=\{ 1,\ldots,n\}$. The Johnson graph $J_{n,m}$ has as vertex set ...
3
votes
0answers
127 views

undirected random graph: common neighbors between two vertices

I have a undirected random graph with node degree distribution $P(k)$, I pick a random vertex $v_0$ and I randomly select a neighbor $v_1$ (the selection is made with uniform probability). What is ...
3
votes
1answer
104 views

What can we prove with infinite graphs that we cannot prove without them?

I asked the following question on CSTheory.SE and was advised that this site might be a more appropriate place for it. Below the line you find the slightly edited question, the original one is here. ...
2
votes
1answer
127 views

Boolean circuits and digraphs

It is well known that connecting NAND gates allows the construction of arbitrary circuits. Furthermore, a NAND gate can be represented as a digraph with four vertices (in order, the two inputs, the ...
0
votes
1answer
768 views

Hamiltonian Cycle Problem

At the moment I'm trying to prove the statement: $K_n$ is an edge disjoint union of Hamiltonian cycles when $n$ is odd. ($K_n$ is the complete graph with $n$ vertices) So far, I think I've come ...
2
votes
0answers
49 views

Partitioning a graph G into at most O(n/k) connected clusters of radius at most k.

Prove that every unweighted n-vertex graph G and every integer k>=1, there exists a partition of G into at most O(n/k) connected clusters of radius at most k. I dont even have a clue on how to strike ...
1
vote
1answer
899 views

Graph where all nodes are pivotal

I am reading a text for an upcoming class Social Network Analysis on Corsera.org and am trying to get a little bit ahead by reading some of the material before class starts. I am working on a question ...
2
votes
0answers
49 views

The effect op graph operations on the chromatic number (Papers/Books)

Can anyone please direct me to a paper or even a textbook which would provide a good read on how graph operations influence the chromatic number of a graph? Thanks.
2
votes
1answer
288 views

Number of sinks/sources in a a random directed acyclic graph

Given an arbitrary graph $G = (V,E)$, such that each vertex v is given randomly a unique integer identifier (call it v). An edge (u,v) is directed from u to v if u > v. This creates a DAG. A ...
-2
votes
1answer
120 views

A Graph Theory Problem

Define $P(S)$ as $$\exists a, b \in S (a - b \in S).$$ Prove that for any subset $S$ of $A = \{1, 2, 3, 4, 5\}$, $P(S)$ or $P(A - S)$ holds. Please prove it using some graph theory.
2
votes
2answers
73 views

Decomposition of graph

Prove that if $G$ is a graph with degree of every vertex at most $3$, then it can be decomposed for graphs $C,T$, where $C$ is a sum of vertex-disjoint cycles and $T$ is a sum of trees. I ...
4
votes
1answer
101 views

Graph for which certain induced subgraphs are cycles

Let us call a graph G $nice$ if for any vertex $v \in G$, the induced subgraph on the vertices adjacent to $v$ is exactly a cycle. Is there anything that we can conclude about nice graphs? In ...
1
vote
1answer
541 views

Strongly connected directed clique, Hamiltonian cycle

Let $G$ be a directed clique. Prove that $$G \text{ has Hamiltonian cycle} \Leftrightarrow G\text{ is strongly connected}$$ $(\Rightarrow)$ is obvious, but I completely don't know how to prove ...
0
votes
1answer
226 views

Explanation of Unweighted Shortest path definition from Introduction to Algorithms by Cormen et al

From Introduction to Algorithms by Cormen et al: We are given a directed graph G = (V,E) and vertices ${u,v}\in V $ and then the define Unweighted shortest path to ...
0
votes
1answer
584 views

What is a subproblem graph in dynamic programming parlance?

I know what dynamic programming is but I do not really understand the concept of subproblem graph for a dynamic programming ? How are they useful ? When solving problem by dynamic programming should ...
1
vote
4answers
2k views

What is the definition of an weighted graph?

In graph theory which one of these two will be called a weighted graph ? A graph where vertices have some weights or vales . A graph where edges have some weights or values . A graph where both ...
1
vote
1answer
56 views

Graph properties characterized by finitely many 'simplest examples'

Recently I heard someone talking about a general result saying that a graph property satisfying certain conditions always is characterizable via a (finite) set of 'smallest examples' (similar to the ...
4
votes
2answers
74 views

Is the cycle graph $C_n$ defined only for $n \ge 3$?

I'm having a hard time seeing what $C_n$ would be for $n = 1$, or $n = 2$. Can someone clear up my confusion?
8
votes
4answers
5k views

Graph theory: adjacency vs incident

Okay, so I think if 2 vertices are adjacent to each other, they are incident to each other....or do I have it wrong? Is this just different terminology. I thought I was totally clear on this for my ...
9
votes
1answer
505 views

What is the significance of the graph isomorphism problem?

It seems that graph isomorphism is an overwhelmingly interesting problem, particularly computationally. Why is that? What are the (theoretical and practical) implication of the existence of an ...
3
votes
2answers
251 views

Smallest Planar Cubic Graph with Non Hamiltonian Edge

I'm looking for the smallest simple planar cubic hamiltonian graph without triangles and with at least one edge that never lies on a hamiltonian cycle. I've got one with triangles ...
7
votes
1answer
825 views

Proof for Heine Borel theorem

I am trying to prove the Heine Borel theorem for compactness of the closed interval $[0,1]$ using Konig's lemma. This is what I have so far: I assume $[0,1]$ can be covered by ...
1
vote
1answer
609 views

Consider a graph G such that at least one vertex v is connected to all other vertices. Prove that G is not bipartite.

Consider a graph G such that at least one vertex v is connected to all other vertices. Prove that G is not bipartite. That's the question, however, I don't think it can be proven. I think there's ...
4
votes
1answer
152 views

Chess tournament, graph

Problem. In chess tournament each player, from all $n$ players, played one game with every another player. Prove that it is possible to number all players with numbers from $1$ to $n$ in such way ...
2
votes
2answers
246 views

For graph $G$, vertices $s,t$ find the shortest path between $s$ and $t$ by weight among all the shortest paths by edges

Given directed graph $G=(V,E)$, two vertices and a weights function $w: E \to R$. In addition we know that there aren't negative cycles in $G$. I need to find a linear algorithm that finds among the ...
1
vote
1answer
132 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 ...
2
votes
2answers
238 views

Shortest paths from $s$ by weight which contain even number of edges

Given a directed graph $G=(V,E)$, and a vertex $s\in V$, for every edge there's an integer weight $w(e)$ (positive or negative), I need to find an algorithm such that for every vertex $v \in V$ it ...
0
votes
1answer
81 views

finding two trees from a graph

The problem is related to check existence of 2 trees of a graph such that: 1)vertices in 2 trees are disjoint and no vertices are missed 2)Any tree edge cannot be a graph edge of original graph. I ...
1
vote
1answer
79 views

What type of graph problem is this?

Lets say I have four group A [ 0, 4, 9] B [ 2, 6, 11] C [ 3, 8, 13] D [ 7, 12 ] Now I need a number from each group(i.e a new group) E [num in A,num in B, num in C, num in D], such that the ...
2
votes
0answers
76 views

Ramsey (graph) theory question with tree and girth

Sorry for the abundance of questions I'm asking. Test is soon... Prove that for every tree $T$ and every $g \in \mathbb{N}$, exist $G$ with girth $g$, so that in any 2-edge-coloring of $G$ there is a ...
1
vote
0answers
237 views

Number of odd cycles in non-bipartite 3-connected graph

By going over the tests of previous years in graph theory, I've come across an interesting (in my opinion) question: $G$ is 3-connected, non-bipartite graph. Prove that $G$ contains at least 4 odd ...
1
vote
0answers
48 views

Unions of edge sets of cycles in a graph

Given a connected graph with minimum degree 3 and a set of edges in this graph, I wish to find the number of decompositions of this edge set into cycles of the graph. I use decompositions in the ...
1
vote
0answers
76 views

Four questions concerning dual graphs

What are the (combinatorial/algebraic) conditions that the dual - resp. the (weak dual) - of a planar graph is unique (independent of its embedding), simple (and not a multi-graph)? Are these ...
1
vote
1answer
114 views

Foam-like graphs

What's the "official" name of a connected planar graph consisting entirely of polygons (cycles), glued together at edges, e.g. - among other things - without "end vertices" (of degree 1) and without ...
3
votes
1answer
61 views

Uniform planar graphs?

What's the name of a planar graph in which every (inner) face has the same number $k$ of vertices? Something like $k$-uniform planar graph? And is there a name for planar graphs in which every face ...
0
votes
1answer
714 views

Using adjacency matrix to calculate the number of hamiltonian paths

I heard that adjacency matrix can be used to calculate the number of k-length paths in a graph. Can't this be used as a way to calculate the number of hamiltonian paths?
2
votes
1answer
231 views

Graph theory and Burnside's lemma

How many are non isomorphic tournaments (directed clique) with $n=5$ vertices? I'm not sure how to understand isomorphism here. This problem was in the set of problems on Burnside's lemma but ...
0
votes
0answers
160 views

Is this proof right? - An $r$-connected graph with even vertices and no $K(1,r+1)$ has a perfect matching

I'm preparing for an exam and I am not sure if my solution to a particular question is viable. Maybe somone can shed some insight? The question: Given an $r$-connected graph $G$ on an even number of ...
0
votes
2answers
77 views

Match covered graph is 2-connected

Seems to be an easy question, but I can't find the right direction. Let $G$ connected graph on at least 4 vertices, such that every edge in it, participates in a perfect matching. Prove that $G$ is ...
1
vote
1answer
244 views

Do the terms “quiver” and “meta graph” refer to the same concept?

Do the terms "quiver" and "metagraph" refer to the same concept? Or is there a distinction I am missing. My sources are Quiver - http://ncatlab.org/nlab/show/quiver Metagraph - ...
3
votes
1answer
339 views

graph that is a edge-disjoint union of trails of even length

An old exercise from my graph theory notes has the following exercise: Let $G$ be a connected graph with an even number of edges and with a non-zero even number $2n$ of vertices of odd degree. ...
1
vote
0answers
197 views

Perfect matching in $r$-connected graph

$G$ is a simple $r$-connected ($r \geq 1$) graph, with even number of vertices. Assume that $G$ doesn't contain $K_{1,r+1}$ as an induced subgraph. Prove that $G$ has a perfect matching. Now, I can ...
0
votes
1answer
304 views

How to find the maxium number of edge-disjoint paths using flow network

Given a graph $G=(V,E)$ and $2$ vertices $s,t \in V$, how can I find the maximum number of edge-disjoint paths from $s$ to $t$ using a flow network? $2$ paths are edge disjoint if they don't have any ...
5
votes
2answers
753 views

Instant insanity question

My question is regarding the necessary conditions that a graph must fulfill to satisfy instant insanity problem. Now take for example the left, right, front and back face colors of the four cubes ...