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
2answers
23 views

Ramsey Numbers involving Cycles, $R(K_3, C_5)$

I've been asked to determine the value of $R(K_3, C_5)$, but I'm having a lot of difficulty putting all the pieces together. We were given the hint of using $R(3,4) = 9$, and I've tried to apply ...
1
vote
1answer
21 views

Steps in a proof from Spectral Graph Theory by Fan Chung

On page 15 of Spectral Graph Theory by Fan Chung, http://www.math.ucsd.edu/~fan/research/cb/ch1.pdf, before eq (1.14) is the step, $\displaystyle || \sum_{i\neq 0} (1-\lambda_i)^s a_i \phi_i ...
4
votes
0answers
23 views

What is the maximum number of edges in an $n$-vertex non-Hamiltonian graph of minimum degree at least $2$?

Q: What is the maximum number of edges in an $n$-vertex non-Hamiltonian (simple) graph of minimum degree at least $2$? This question relates to Maximum number of edges in a non-Hamiltonian graph ...
5
votes
0answers
24 views

How many hamilton paths can a non-hamiltonian graph have?

What is the maximum number of hamilton paths a graph with $n$ vertices can have without having a hamiton cycle ? If my turbo pascal program works well, the first few values for $3,4,...$ vertices ...
0
votes
0answers
41 views

How to prove Cayley's formula by double counting? [on hold]

How to prove Cayley's formula for the number of trees on $n$ labeled nodes, using double counting? I have tried to google it and found this proof, but I cannot understand the proof. Please, can ...
0
votes
0answers
16 views

doubt regarding power of graph

could you help me in clarifying a doubt regarding how to find square of a graph g from graph g.the doubt occurs on 15th page of the document which I have shown you by the link given.the doubt is that ...
2
votes
0answers
28 views

Decomposing the Complete Graph into Forests

Which spanning forests can we partition the complete graph $K_n$ into? I am primarily interested in partitions into one fixed isomorphism class of forest. I'm also assuming whatever divisibility ...
0
votes
1answer
29 views

Proof of Floyd Cycle Chasing (Tortoise and Hare)

I am looking for a proof of Floyd's cycle chasing algorithm, also referred to as tortoise and hare algorithm. After researching a bit, I found that the proof involves modular arithmetic (which is ...
2
votes
1answer
33 views

Graphs: probability of two vertices, chosen at random, of being connected by a link

If I choose the vertices h and k in a simple graph uniformly, I know the probability of them being joined by an edge is $ \frac{2e}{n(n-1)} $ , where: e is the number of edges in the graph, n is the ...
3
votes
1answer
27 views

Shortest path between two vertex

How we can find Shortest path between two vertex in a weighted directed acyclic graph that has positive and negative weight. in O(|V|+|E|)? thanks to all.
0
votes
1answer
27 views

Independent cycles in undirected graph

What is the algorithm that allows me to determine the independent cycles in an undirected graph. For example, in the figure below: The independent cycles: [2-12-4-5-13-2] [4-5-6-4] [4-10-11-7-6-4] ...
0
votes
2answers
17 views

Conflicting definition of eulerian graph and finite graph?

I'm reading Van Lint and Wilson: A Course in Combinatorics. There is one part of the book where he defines a finite graph: A graph is finite when both E(G) and V (G) are finite sets. Theorem ...
0
votes
1answer
23 views

Random walks on connected finite graphs

On a finite connected graph if a random walked is choosing the next vertex uniformly at random from among the edges of its current vertex, then it looks quite obvious to me that given an infinite walk ...
4
votes
0answers
71 views

Is there a name for graphs with the following property?

The property of the graph is the following: For any vertex, there is a hamiltonian path starting with this vertex, but the graph is not hamiltonian. The following graph is a small example: ...
2
votes
1answer
50 views

How many ways are there to color the $H$-shaped tree with $3$ colors such that each color is used exactly twice?

How many ways are there to color this graph with the following constraints? We have three colors: blue, red, green, and we require that the number of nodes of color green is 2, and blue 2, and red ...
1
vote
0answers
12 views

Kronecker product and the vec operator: confusion on proof of vec(AXB) = (transpose(B) ⊗ A) vec(X)

I was reading up on Kronecker products and vec operator from couple of sources and landed on the equation: vec(AXB) = (transpose(B) ⊗ A) vec(X) suppose ...
3
votes
1answer
56 views

Which are the natural morphisms between binary relations?

Which properties should morphisms $\alpha$ between binary relations have? $ (1) \qquad R \overset \alpha \longrightarrow R\,', \;R\subseteq X\times Y, \;R\,'\subseteq X'\times Y' $ Can those ...
6
votes
1answer
61 views

Proof that there is no closed knight tour on a $3\ \times\ 8$ - board

I want to prove that there is no closed knight tour on a $3\ \times\ 8$ - board by deleting $s$ vertices of the corresponding knight graph to get a graph with more than $s$ connected components ...
0
votes
0answers
17 views

Sparsification of a graph - with constraints

Say I have a graph (in matrix form) in which every vertex is connected to every vertex in some way. Instead of considering every connection, I would like to prune the graph such that it becomes more ...
0
votes
1answer
22 views

Maximal-size set of disjoint edges

Inspired by a "real-world" puzzle (actually, an unimportant aspect of a free-to-play game someone I know is playing)... Given an arbitrary (finite) undirected graph, I want to compute a ...
1
vote
1answer
21 views

A graph with minimum degree $k+2$ contains any $(k+3)$-vertex tree as a subgraph?

Let $k$ be a positive integer and let $T$ be a tree of order $k+3$. If $G$ is a graph with minimum degree at least $k+2$, prove that $G$ contains a subgraph isomorphic to $T$. Any solutions or hints ...
3
votes
1answer
53 views

Details from a Proof that a Tournament has Property $S_k$

(Edit: While the context is not central to my question, I decided to include it anyway to make the question a little more searchable.) Some technical details are omitted from a theorem in Alon and ...
1
vote
1answer
55 views

Determine cycle from adjacency matrix

Is there a way/algorithm to determine if there is a cycle in a graph if I only have the adjacency matrix and can not visualize the graph?
1
vote
0answers
22 views

Transforming spanning sub-graphs

I have the following question: Suppose we have a finite graph $G=(V,E)$. Now take two arbitrary spanning sub-graphs, i.e. $G_1 = (V,E_1)$ and $G_2=(V,E_2)$ with $E_1,E_2 \subseteq E$. Suppose we ...
1
vote
0answers
39 views

A combinatorial enumeration problem on graph

Let $G$ be a complete graph of order $n$, we now delete $i$ edges from it, then how many complete subgraphs are there with order $m$ in the rest graph? (You can assume $m\ll n$ and $i\ll m$ if ...
0
votes
0answers
18 views

Pascal's Identity and Trees

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
0
votes
2answers
28 views

Upper and lower bound on graph

Find upper and lower bound for the size of a maximum (largest) independent set of vertices in an n-vertex connected graph, then draw three 8-vertex graphs, one that achieves the lower bound, one that ...
1
vote
1answer
21 views

Graph with small average degree has two vertices of small degree

Suppose $G$ is a graph and its average degree $\epsilon(G) = \frac{2|E(G)|}{|V(G)|}$ is in the interval $0 < \epsilon(G) < 2.$ Then clearly $G$ has one vertex of degree at most $1.$ Reading ...
2
votes
1answer
47 views

graph theory - why don't this graph exist?

Consider a tournament graph on $n$ nodes. Why does a graph with the following property not exist? Two nodes have the same outdegree and the other $n-2$ nodes have different outdegrees.
0
votes
1answer
35 views

Hanoi Algorithm With Different Nodes

http://en.wikipedia.org/wiki/Tower_of_Hanoi I need help developing a Hanoi algorithm which follows the same rules as the standard game, however the nodes that are transversed is different. In this ...
0
votes
1answer
38 views

Defining a group from edge set of graph

I consider three islands represented by vertices V and the travel routes by ship are represented by the edges E. Here G=(V,E). I consider the non-empty set E and define the binary operation ...
-1
votes
1answer
17 views

Prove: let v be a vertex in a tree T. Then w(T-v) = d(v) [on hold]

w(T-v) means the component of T without(minus) v and d(v) means degree of v. it says that they are equal.
2
votes
0answers
31 views

Directed multigraph with numbered edges

Let we have a directed multigraph such that or every its vertex the set of edges from this vertex is finite and ordered (in other words, numbered $1,\dots,n$). I need this construct to describe ...
0
votes
0answers
26 views

Logic behind Force-directed graph drawing/layout

Here are the prerequisites for what I'm trying to do: I have n nodes (rectangles) in a 2D plane, that are evenly spaced (can have any x/y coordinates) Each node has width w and height h (each node ...
0
votes
0answers
10 views

Katz centrality and Node removal

I'm looking for any results about how Katz centrality changes when a given node is removed from a graph. For instance, if I define a function to be the average of the Katz centrality of the remaining ...
2
votes
0answers
19 views

Minimum number of transitive paths in tournament

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if ...
0
votes
0answers
26 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
1
vote
2answers
56 views

Solving a graph [closed]

Prove or disprove: there exists a simple graph with 13 vertices, 31 edges, three 1-valent vertices, and seven 4-valent vertices. I need your help to solve this question.
0
votes
1answer
33 views

Is this a correct planar graph testing algorithm?

I want to know whether the below algorithm is correct for testing planr graph: step 1. Remove every degree-1 vertex and the edge that contains it. step 2. Remove every degree-2 vertex and replace ...
2
votes
0answers
36 views

IS this proof by induction of the hand shake lemma correct?

Proof by induction that the sum of degrees of vertexes in an undirected graph equals two times the number edges, where $V$ is the set of vertexes and $E$ is an edge multiset: $$\sum_{v ∈ V} deg(v) = ...
0
votes
2answers
29 views

Minimum cut in a graph does not change when the weight of all edges is increased by one

Suppose we have a Graph $G$ in which weight of all edges is $> 1$ (positive). If we increase weight of all edges by one, why does the minimum cut $(S, T)$ of $G$ into two graphs remain the same? ...
0
votes
0answers
14 views

Geometric dual graph

It is well known the notion of geometric dual graph. Let $G^*$ be the geometric dual of a planar graph $G$. I need the proof that $(G^*)^* \cong G$ , where can I find it ?
2
votes
1answer
70 views

Using a corollary of Tutte's theorem to prove a statement

I've been asked to prove that any graph $G$ which is $n$-connected, $n$-regular, and has even order has a one-factor. A hint that we were given for proving this was a corollary to Tutte's theorem, ...
0
votes
1answer
29 views

Graph homomorphism, and how to proof?

I want to know whether there exists a homomorphism from this graph (below in the image) to $K_5$ (complete graph with 5 vertices). If so, how can I prove this relationship? Since homomorphism is a ...
1
vote
1answer
31 views

can dijkstra's algorithm be applied as it is for undirected graph

I am wondering why can't Dijkstra's algorithm be applied as it is for undirected graphs. I mean instead of adding 2 directed edges to make it equivalent to a directed graph , why wouldn't it work if ...
7
votes
1answer
82 views

Graphs with uncountably many vertices

Let $ \mathcal{H}$ be the class of all graphs with at most $ 2^{\aleph_0}$ vertices not containing a complete subgraph of size $ \aleph_1$. Show that there is no graph $ H \in \mathcal{H}$ such that ...
0
votes
1answer
41 views

Find if it is possible to draw a closed (cycle; not a path) continuous line…

... that crosses exactly once (only once) each interior line segment of the rectangle, whilst staying inside the rectangle for these 2 rectangles. My immediate reasoning was to remove all the outside ...
0
votes
2answers
40 views

The maximum no. of edges in a DISCONNECTED simple graph…

... on n vertices when it is not connected being equal to (1/2)(n - 1)(n - 2)... I can see that for n = 1 & n = 2 that the graphs have no edges... however I don't understand how to derive this ...
1
vote
4answers
41 views

Notation for two-vertex graph with m edges

Is there standard notation for the graph on two vertices with $m$ edges between them?
1
vote
1answer
21 views

Kirchoff Matrix -Tree Theorem

I'm reading a proof of the Kirchoff Matrix -Tree Theorem: If $G$ is a simple connected graph, $D$ the diagonal matrix with the vertices' degrees and $A$ the adjacency matrix, then in $M = -A+D$ ...