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

2
votes
0answers
17 views

spring representation of graphs

Suppose we have a finite graph $G$ which we want to embed in ${\bf R}^d$; fix the positions of some nodes and connect all the nodes of the graphs with ideal springs of varying strength; (i.e. there is ...
0
votes
0answers
9 views

infinite graph & its complement with complete subgraph

An infinite graph is a graph whose vertex set is infinite. Prove that for any infinite graph G either it or its complement contains an infinite complete subgraph. I have tried it and here's my ...
1
vote
1answer
14 views

Show that for each $n \geq 2$, $Q_n $ is Hamiltonian

I know that $Q_n = Q_{n-1} \times K_2$. So I let $U=\{u_1,u_2,\dots, u_{n-1}\}$ be the set of vertices of the first copy of $Q_{n-1}$ and $V=\{v_1,v_2,\dots, v_{n-1}\}$ be the set of vertices of the ...
2
votes
0answers
9 views

The cycle space and cut space are orthogonal complement

I am trying to prove the following theorem: Let $G$ be a graph. The cycle space and cut space are orthogonal complement if and only if the graph $G$ has an odd number of spanning tree. My attempt: I ...
1
vote
0answers
11 views

Show that if $H$ is a spanning subgraph of a non complete graph $G$ then $t(H) \leq t(G)$

Show that if $H$ is a spanning subgraph of a non complete graph $G$ then $t(H) \leq t(G)$ Since $H$ is a spanning subgraph of a non complete graph $G$, $V(H) = V(G)$ and $E(H) \subset E(G)$, so ...
0
votes
0answers
7 views

similarity measure between sentences

I would like to know how the normalization factor was evaluated in the paper (http://dl.acm.org/citation.cfm?id=1220627). Also in the example "The church bells no longer rung on Sundays" I noticed ...
1
vote
1answer
22 views

Show that if $G$ is a graph of order $n \geq 2$ for which $\kappa (G) \geq \alpha(G)-1$, then $G$ has a Hamiltonian path.

Show that if $G$ is a graph of order $n \geq 2$ for which $\kappa (G) \geq \alpha(G)-1$, then $G$ has a Hamiltonian path. Theorem 3.15: Let $G$ be a graph of order at least 3. If $\kappa(G) \geq ...
0
votes
0answers
11 views

Clarification on labelled graphs?

I am ready Bondy and Murthy's Graph Theory: And here is the Figure $1.10$: I don't understand what are these three labelled graphs for $P_3$, in the figure, I see $4$ different graphs: ...
1
vote
0answers
31 views

Masters' thesis in algorithmic graph theory

I would like some ideas on topics in algorithmic graph theory which would be suitable for a masters' thesis. What sort of problems would be suitable for this level? Because it is at masters' level, no ...
1
vote
1answer
41 views

Can books be arranged into bags?

I'm trying to find an algorithm (sub exponential) to answer the following question (informal): given a (finite) set of distinct books of different (positive integer) sizes and a (finite) set of bags ...
0
votes
1answer
16 views

Calculating the “edge” distance between two points

I was wondering if measuring the "edge" distance $d_e$ between two points like this had a formal name, and if it could be calculated directly? In both examples you are not allowed to cross diagonally ...
0
votes
0answers
17 views

Maximum flow between three edges in a flow network

I am assuming that the following fact is true in a flow network N(G(V,E) ,s,t,c ) Let us say A,B,C belongs to E in a finite directed graph G. F(x,y) is maximum flow in the network N, then the ...
0
votes
1answer
14 views

Transition matrix to graph

Is there a program which can given a transition matrix $P$ draw a graph from a it? The transition matrix is also known as stochastic matrix and probability matrix see ...
1
vote
1answer
39 views

Prove that if $deg (v) > \frac{k}{2}$ for every $v \in V(G)$ then $G$ is Hamitonian.

Let $G$ be a bipartite graph with partite sets $U$ and $W$ such that $|U|=|W|=k \geq 2$. Prove that if $deg (v) > \frac{k}{2}$ for every $v \in V(G)$ then $G$ is Hamitonian. Dirac's theorem : ...
1
vote
0answers
25 views

Find a neccessary and sufficient condition for $G$ to be Hamiltonian

a) prove that $K_{r,2r,3r}$ is Hamiltonian for every postive integer $r$ b) prove that $K_{r,2r,3r+1}$ is Hamiltonian for no postive integer $r$ c) Let $G=K_{n_1 , n_2, \dots ,n_k}$ be the complete ...
4
votes
0answers
42 views

Dividing tournament into “equal” groups

In a tournament of $n$ teams, each team plays all other teams exactly once, with no draw. For which $n$ is it always possible to divide all teams into several groups so that each group of teams won ...
1
vote
1answer
27 views

A simple problem of graph theory.

There are how many $4$ vertices connected graphs not including a triangle? My try:I made 3 such graphs.Is it maximum possible number of such graphs or there are many others?Is there any formula in ...
1
vote
0answers
19 views

Show that $G$ is $2$-connected but not necessarily Hamiltonian

Let $G$ be a graph of order $n\geq 3$ having property that for every vertex $v$ of $G$, there is a Hamiltonian path with initial vertex $v$. Show that $G$ is $2$-connected but not necessarily ...
0
votes
0answers
12 views

Find mimimum hamiltonian path with a “Magic” SP algorithm

I want to find a minimum Hamiltonian path in a graph $G=(V,E)$ with edge cost $c:E\rightarrow \mathbb{R}^+$ from $s$ to $t$ with $s,t \in V$. Suppose we have a Magic algorithm that yields a shortest ...
1
vote
1answer
31 views

Prove that if $G$ and $H$ is Hamiltonian then $G \times H$ is Hamiltonian

Prove that if $G$ and $H$ is Hamiltonian then the Cartesian product $G \times H$ is Hamiltonian Theorem 3.16: If $G$ is Hamiltonian and $S$ is the vertex cut then $$k(G-S) \leq |S|$$ This ...
0
votes
1answer
17 views

How many 1-regular graphs can be produced by deleting edges from a even complete graph?

Given a complete graph $K_n$ where $n > 1$ and $n$ is even, how many distinct 1-regular graphs can be produced by only deleting edges? By "distinct" I mean the vertices are numbered or taken based ...
2
votes
1answer
45 views

How to Apply Hall's theorem in this question? [on hold]

A table with $m$ rows and $n$ columns is filled with nonnegative integers such that each row and each column contains at least one positive integer. Moreover, if a row and a column intersect in a ...
0
votes
0answers
11 views

Increasing the speed of a depth first search.

I am looking for ways to increase the speed of a depth first on a graph when trying to find a path from a source node to a destination node. One thing I have tried is to perform a bidirectional ...
1
vote
2answers
19 views

Help with proof of the existance of a graph produced from deleting edges

Prove that every connected graph with an even number of vertices can be transformed into a graph with uniform degree 1 by only deleting edges. I have tested this with pen-and-paper and it seems to be ...
1
vote
0answers
9 views

possible embeddings for a $2$-connected planar graph

When I asked the question "cycles and faces in planar graphs", I learned that the numbers of vertices in the faces are not unique, if the planar graph is only $2$-connected. My question now is : How ...
1
vote
0answers
11 views

Examples of sequences of graphs with different order of Cheeger constant and spectral gap

According to Cheeger's inequality, the bottleneck ratio/Cheeger ratio $\Phi_*$ of a graph and the spectral gap $\lambda$ of its adjacency matrix satisfies $$\Phi_*^2/2 \leq \lambda \leq 2\Phi_*. $$ ...
1
vote
2answers
14 views

How can I prove that a graph with a required amount of edges per node is invalid?

For the following example I assume that no node may be connected to itself. Nodes: A, B, C, ...
0
votes
1answer
24 views

Proving two graphs are isomorphic in polynomial time - Bondy/Murty - Graph Theory Page 6

I am trying to do the below problem: Now I can't see how one does this. I know you can explicitly show the bijections, but I can't see an easy way to do this, since it is $3\text{-regular}$. I ...
0
votes
0answers
29 views

Does $\beta(G)=\alpha'(G)$ always?

Does there exist a graph where the minimum vertex cover does not equal the size of the maximum matching? I'm thinking that if it does, then it cannot be a bipartite graph and so it contains an odd ...
0
votes
0answers
13 views

Markov chains: identifying a nonregular transitional matrix

I am currently TA'ing for a course in which the students are soon to learn about Markov chains and stochastic matrices. During the sections, it refers to the possible existence of a stable state and ...
-1
votes
1answer
13 views

Graph theory problems about vertices and interior angles.

I have three problems of graph theory: $1.$We have a $10$ gon then maximum number of acute angles that we can make is? $2.$We have $5$ vertices then how many connected trees we can make? $3.$How ...
-2
votes
0answers
20 views

Number of triangles in a graph and its complement

Let $G$ be a simple graph with $|V(G)|=n$ and $|E(G)|=e$. let $T$ be the number of triangles in $G$. Show that $T ≥\frac{4e}{3n}(e-\frac{n^2}4)$ and find a larger possible lower bound for ...
0
votes
2answers
22 views

A simple problem of graph theory about the degree of vertices.

A graph has $7$ vertices and $10$ edges then which is true? $(I).3$ vertices of degree $4$ and $4$ vertices of degree $2$. $(II).2$ vertices of degree $5$ and $5$ vertices degree $2$. $(III).$Every ...
0
votes
1answer
19 views

$3$-connected non-hamiltonian graph with at most $3$ independent vertices

Is there a $3$-connected non-hamiltonian graph with at most $3$ independent vertices ? I checked the graphs upto $9$ vertices and the cubic graphs upto $18$ vertices and did not find such a graph. ...
3
votes
1answer
23 views

Find maximum number of nodes in a regular graph of degree 4 and diameter 2

In $n$ nodes directed graph, every vertex has in-degree and out-degree equal to $4$. If every vertex is reachable from every other vertex directed by a path of length at most $2$. How can we find ...
1
vote
0answers
18 views

Mapping graphs to themselves, e.g. the meta-graph

I'm looking for any prior work on a (for lack of a better word) meta-graph. Let $M=(V,E)$ be a a meta-graph with vertex and edge set $V,E$. The meta-graph is formed by mapping a set of graphs $G = ...
0
votes
1answer
20 views

The complexity of Depth First Search

Can anyone tell me what's the complexity of Depth First Search? I have no idea about what does mean by the complexity.
0
votes
4answers
56 views

Prove that $G$ has at least $q-p+c$ cycles.

I need your help with this question: Suppose that a graph $G$ has $p$ vertices, $q$ edges, and $c$ components. Prove that $G$ has at least $q-p+c$ cycles. I don't know how to prove that.
0
votes
0answers
17 views

Breaking Ties Alphabetically Using Kruskal's Algorithm

Kruskal's Algorithm picks the next edge simply by picking the lightest edge. Doesn't that make breaking ties alphabetically impossible? If I had a graph where two edges ...
1
vote
2answers
55 views

Proving that every connected graph has a vertex whose removal will not disconnect the graph.

I have not done much proofs before this and need some guidance. I know that for a simple graph such as this : node - node - node -node Removing the first and ...
1
vote
0answers
9 views

Max flow on undirected graph with constrained edges

I've been trying for a while to develop an algorithm that counts the maximum number of disjoint vertex paths in a graph, but with an addition of "forced paths". Forced paths are here marked with bold ...
2
votes
1answer
54 views

Are “almost all” graphs hamiltonian?

Let $$p(n):=\frac{\text{number of hamiltonian graphs with $n$ nodes}}{\text{number of graphs with $n$ nodes}}$$ Since $883156024$ of the $1018997864$ graphs with $11$ nodes are hamiltonian, we have ...
0
votes
1answer
27 views

decomposition of graph to cycle and cut space

Let $G$ be a graph. I want to show that $E(G)$ is disjoint union $C\cup D$ where $C$ and $D$ belong to cycle and cut space respectively.
0
votes
1answer
11 views

Extremal graph theory

Determine ex(n,2K2) for every n. (2K2 means a pair of vertex-disjoint edges, ex(n,H) = max{e(G): |G| = n is H-free}) I think the answer might be n+1 choose 2 but I am stuck on where to start.
0
votes
1answer
14 views

Graph Theory (Vertex Connectivity)

Show that for any edge $e\in E(G)$, $κ(G−e)\geκ(G)−1$. ($e$ is an element of the edge set, $κ(G)$ is vertex connectivity) I think this follows from Mengers theorem, but I am having trouble seeing ...
5
votes
1answer
40 views

Graph DFS, BFS and some inference

Suppose G is a connected, undirected graph with at least 3 vertexes. we know the order or visiting the vertexes in DFS and ...
0
votes
1answer
22 views

Proof verification: (Pretty pictures :) )Showing two graphs are not isomorphic. Bondy/Murty - Graph theory Page 5

I want to show the below two graphs are not isomorphic. Treat the left as graph $\bf G$ and the right as graph $\bf H$. $\bf G$ and $\bf H$ are not isomorhpic: Although we have a bijective mapping ...
0
votes
2answers
21 views

If $G$ is simple, then $\epsilon \leq {v \choose 2}$ - Bondy/Murty - Graph Theory with Applications Page 4

Question: Does this proof hold? Is this a bad proof? Any nicer proofs that don't rely on other theorems? Notation: $\epsilon$ - Number of edges $v$ - Number of vertices G - Here, any Graph ...
0
votes
0answers
23 views

Problems in extremal graph theory [on hold]

Determine ex(n, 2K2) for every n. (Here 2K2 means a pair of vertex-disjoint edges).
-1
votes
0answers
21 views

Graph Theory - Paths

A Θ-graph is a graph consisting of two vertices x and y joined by three paths that share no vertices other than x and y. Prove that any Θ-graph contains an even cycle