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
0answers
19 views

Deleting any edge leads to a unique Hamiltonian cycle.

The Markström graph has the property that deleting any edge makes the Hamiltonian cycle unique. Other than $K_4$, what other graphs have this property? What is this property called?
0
votes
1answer
65 views

Is there an easy method to determine if a graph is planar or not?

So, I have this graph and I can't find a subgraph that is K5 or K3,3 to use the kuratowski theorem .Is there another way to determine if it is not planar without coloring?
1
vote
0answers
19 views

A directed graph and existence of vertex of finite degree

Let $\{1,...,k\}$ be a set of vertices of a directed graph, with no multiple edges. We say that paths $p$ and $f$ are disjoint by interior vertices if they are disjoint or have a common first or last ...
0
votes
0answers
25 views

Konig's theorem and perfect graphs

I want to understand why perfect graphs are so named and why are they relevant. Consider the following statement from wikipedia's article on Konig's theorem. A graph is perfect if and only if its ...
1
vote
1answer
22 views

Number of cycles of length 4 in K7

The answer to this I believe is $1/2$ * $7C3$ * $3!$ How do you arrive to this answer? I understand the $1/2$ since the graph is undirected, but nothing else. Isn't there 4 ways to choose a cycle of ...
1
vote
0answers
17 views

Directed Graph $D$ has a Directed Path of At Least $\chi_u$ vertices

I've been working on some problems related to directed graphs in my computer science course, and I have been somewhat stumped on this one particular problem. Take a directed graph $D$, and consider ...
1
vote
1answer
37 views

Determine the number of graphs on the vertex set $\{1, 2, 3 , 4, 5\}$, every vertex is incident to at least one edge.

I have the problem of determining how many graphs from the set $\{1, 2, 3, 4, 5\}$ there are, given the property that every vertex is incident to at least one edge. The at least one part of the ...
1
vote
0answers
24 views

Does the sweep line Algorithm produce a maximum independent set?

We know that a sweep line algorithm or plane sweep algorithm is a type of algorithm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space [Wikipedia] Sweep ...
0
votes
0answers
25 views

In a directed graph, every vertex has exactly seven edges coming in. What can one always say about the number of edges going out of its vertices?

1.Exactly seven edges leave every vertex. 2.Exactly seven edges leave some vertex. 3.Some vertex has at least seven edges leaving it. 4.The number of edges coming out of vertex is odd. I am unable ...
0
votes
0answers
15 views

My question is about Cayley graphs where the Cayley set is any set of transpositions.

I want to show that if $S$ is any subset of $Sym(n)$ such that $S$ contains only transpositions, then the Cayley graph $X=Cay(Sym(n), S)$ is bipartite. I have figured out that the vertices in $X$ ...
0
votes
1answer
30 views

Negation of a statement

What would be the negation of the following statement? "There exist vertices $u$ and $v$ of $G$ such that the edge $x$ is on every path joining $u$ and $v$." Would it be, "there exist vertices $u$ ...
0
votes
0answers
39 views

Find the chromatic polynomial of the $3 \times 3$ grid graph

Find the chromatic polynomial of the $3 \times 3$ grid graph. Maple give the answer $$ \lambda\, \left( \lambda-1 \right) \left( {\lambda}^{7}-11\,{\lambda} ...
0
votes
1answer
12 views

How to prove that maximal independent set is equal to maximum independent set in an interval graph?

Introduction: An interval graph $IG$ is a set of intervals on the line, the corresponding interval graph represents each interval with a vertex. if they overlap then the intersection between the ...
2
votes
0answers
108 views
+50

Is there matrix representation of the line graph operator?

I had the need to calculate the adjacency matrix $L$ of the line graph of a certain planar $k$-regular graphs $G(n,e)$ ( $n$ vertices and $e=\frac k2 n$ edges) given its adjacency matrix $A_G$. Here I ...
0
votes
0answers
18 views

Chromatic polynomial of simple graph

Suppose I know the chromatic polynomial $P(G, \lambda)$ of the graph $G$. Can we express the chromatic polynomial of the graph $G'$ in terms of $P(G, \lambda)$ and $\lambda$? I have tried to ...
1
vote
0answers
22 views

Pseudo vertex-transitive graphs

I'm investigating finite, simple graphs with the following property: For each degree $d$ of $G$, the subgraph induced on all vertices of degree $d$ is vertex transitive. In particular, I'm ...
0
votes
1answer
63 views

Why is the Prüfer sequence in a labeled tree always unique?

The Prüfer sequence (also Prüfer code or Prüfer numbers) of a labeled tree is a unique sequence associated with the tree. as we can see from the picture there is a unique sequence {4,4,4,5} # but ...
-2
votes
0answers
14 views

Parallel Luby Algorithm för finding Maximal independent set

This the Algorithm of Luby: MIS Luby Algorithm This Algorithm at the end spent O(log n). I want to understand why exactly O(log n), I need also a mathematical prove of this. Also How many ...
2
votes
0answers
30 views

Shortest Path with use of matrix algebra

I have a directed graph $G = \{V, E\}$ with a source ($s \in V$) and a sink ($t \in V$) (let the other two vertices be $p$ and $q$) represented by an adjacency matrix e.g.: $$ \begin{bmatrix} 0 ...
1
vote
1answer
14 views

Add one edge to the graph such that the graph will not be 3-colourable

Could you guys help me solve this example? The question is, whether it is possible to add one new edge such that the resulting graph is not 3-colourable and prove it. I was trying to find a way to ...
2
votes
1answer
11 views

Add edge such that resulting graph is 2-degenerate

I'm preparing for an exams and I can't find out how to solve this kind of examples. The question is, whether it is possible to add two new edges into the graph such that the resulting graph is ...
1
vote
1answer
25 views

Proving in planar graph

So I have a connected triangle-free planar graph - let's name it G. So I have proven that there exists a vertex V $$deg(V)\leq 3$$ I proved that using $$m\leq 3n-6$$ where $$n=|V(G)| , m=E(G)$$ along ...
0
votes
0answers
14 views

Characteristic polynomial of a graph and structure function of a graph?

The characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. It is a graph invariant, though it is not complete: the smallest pair of non-isomorphic graphs ...
0
votes
0answers
34 views

Minimum paths on graph with probabilistic costs

Consider a graph where costs on arcs are random variables with normal distribution and mean/variance that are themselves random variables (they are estimated from finite sample). The graph is strongly ...
1
vote
1answer
58 views

Uses of Ramsey Theory in Astronomy?

In the last paragraph of a Scientific American article of July 1990 that can be found here http://www.math.ucsd.edu/~ronspubs/90_06_ramsey_theory.pdf Graham and Spencer write "Today we can easily ...
1
vote
0answers
13 views

Decompose a flow network into several trivial flows

Let $f$ be a flow in (a directed) network $G$. Show that it is possible to express $f$ as a sum of another flow $f_0$ which value is 0, and at most $|E|$ flows, each of which is trivial - i.e. flows ...
0
votes
0answers
17 views

Sparsifying a weighted complete graph

Sparsifying a graph $G=(V,E)$ using effective resistance method [as described in http://arxiv.org/abs/0803.0929 ], requires the existence of a Laplacian solver which can be used to calculate the ...
0
votes
2answers
32 views

How to check if a digraph is strongly connected with its adjacency matrix?

Given a digraph G and its adjacency matrix A, which is the easiest way to check if it is strongly connected? In the case of an undirected graph I should check that the matrix $ ...
0
votes
1answer
47 views

Graph theory: strong regular graph

A simple graph G which is neither empty nor complete is said to be strongly regular with parameters $(v,k,λ,μ)$ if: v(G)=v; G is k-regular; any two adjacent vertices of G have λ common neighbours, ...
3
votes
2answers
96 views

On the Usual Orientation of Cubic Graphs in Random Construction of Riemann Surfaces

In "Random Construction of Riemann Surfaces", Robert Brooks and Eran Makover say : Definition 2.1 A left-hand turn path on $(\Gamma, \mathcal O)$ is a closed path on [the cubic graph] $\Gamma$ ...
0
votes
0answers
35 views

Connectivity of a complete graph with one vertex

Consider the graph having just one vertex and no edges.I only know that it is 0-connected graph and every disconnected graph is 0-connected. So, I was wondering whether the graph K1 is connected or ...
0
votes
0answers
25 views

Kuratowski's theorem proof: Flappable bridges

I have a doubt concerning the proof of Kuratowski's theorem. The proof I am reading from is from Combinatorial Problems and Exercises by Lovasz. (Pg 299-301). We are given a graph $G$ which is a ...
1
vote
0answers
25 views

Finding the Chromatic Polynomial for the wheel graph $W_5$

Let $G$ be a graph and let $k \in N$. The chromatic polynomial $P_G(k)$ is the number of distinct $k$-colourings if the vertices of G. Standard results for chromatic polynomials: 1) $G = ...
1
vote
1answer
51 views

Optimization problem on graph with weights on nodes and edges

I am solving a problem where I have a complete undirected graph with weights on the nodes and on the edges. The weight on the node represents a profit that you obtain if you select that node. The ...
2
votes
1answer
33 views

How to prove that there is a monotone path in a graph with a length of greater or equal to average degree?

Let G be a graph with M edges, labeled by the numbers 1, 2, . . . , M. A monotone path is a path along which the labels of the edges create a monotone sequence. Show that there exists a monotone path ...
0
votes
1answer
28 views

proving $E \leq \frac{(n-k+1) \cdot (n-k)}{2}$

I'm trying to prove something about graph theory, but I'm not sure if I'm thinking in the right direction. Let $G$ be a simple graph, that is a graph without multiple edges and loops, let $n$ be the ...
0
votes
0answers
29 views

Show With High Probability $G_{n, p}$ has an induced path of length $(\log(n))^{1/2}$

The problem on which I am working states: Let the probability $p = d/n$ where $d > 1$. Show that with high probability, $G_{n, p}$ contains an induced path of length $(\log(n))^{1/2}$. My ...
0
votes
2answers
28 views

Every connected graph contains a spanning tree

If we consider two vertices connected by two edges, then this graph doesn't contain a spanning tree. Then what is wrong with the theorem?
0
votes
1answer
22 views

Example for adjacency matrix of a bipartite graph

Can someone explain to me with an example how to create the adjacency matrix of a bipartite graph? And why the diagonal elements of it are not zero? Thanks.
0
votes
2answers
19 views

Given a forest, adding k edges would result in a cycle Proof

Assume you have a forest with k connected components. Prove that if you added $k$ edges, you would obtain a cycle. I’m thinking these facts/theorems may be useful... In a forest, each component ...
1
vote
1answer
30 views

$G$ a maximal simple planar graph with $n$ vertices, $m$ edges and $ki$ vertices of degree $i$. Show that $\sum_{i= 1}^{n-1}(6-i)k_i = 12$.

$G$ is maximal simple planar graph with $n$ vertices and $m$ edges. There are $ki$ vertices of degree $i$, for $i = 1, \dots, n-1$. Show that $\sum_{i= 1}^{n-1}(6-i)k_i = 12$. I got the following ...
0
votes
1answer
8 views

Graph theory: Proof that if the graph G(V1V2,E1E2) is conntected then the intersection (V1V2) is not empty.

I'm attempting to prove the following with contradiction. Unfortunately i'm not sure if my deduction is flawless in this one. Given: $G_1=(V_1,E_1),\quad G_2=(V_2,E_2),\quad G=(V_1\cup V_2,E_1\cup ...
1
vote
1answer
62 views

The four colour theorem

I have been reading about the four colour theorem and the fact that it is proved using a computer. My question is whether it is likely that we will ever achieve a proof without the use of a computer? ...
2
votes
1answer
25 views

Can you create non transitive dice for any finite graph?

Let's say you have a finite directed graph, with no two nodes that point at each other. Can we assign each node a dice, so that each node beats the node it is pointing at. This is easy for acyclic ...
1
vote
1answer
53 views

Eulerian and Hamiltonian cycles at the same time

I want to ask if it's possible for a graph to have both Eulerian and Hamiltonian cycles at the same time? And what will happen with graph's connectivity? Could connectivity k(G) be k(G) > 1 ?
1
vote
1answer
20 views

Show that there is a path of length k in G

Let G be a connected simple graph with $n \geq 3$ vertices. Suppose that there is a positive integer $k \leq n$ such that $d(u) + d(v) \geq k$ for every pair of non-adjacent vertices $u$ and $v$. Show ...
0
votes
0answers
18 views

Prove that in any connected graph there is a closed walk which traverses each edge exactly twice

Prove that in any connected graph there is a closed walk which traverses each edge exactly twice. There is a nice solution by creating a new graph $G'$ in which we have replaced each edge of $G$ by ...
0
votes
1answer
22 views

Prove that no vertex can be cut vertex of both G and its complement

"Show that if $v$ is a vertex of a simple connected graph $G$ then $\overline{G} - v = \overline{G-v}$. Also proof that no vertex can be a cut vertex of both $G$ and $\overline{G}$." I have proved ...
5
votes
0answers
157 views

Mapping $\Delta(2,2,2)\mapsto \Delta(4,4,2)$…

Looking at the images below, you recognize that the adajency matrix of the graph $A_G$ splits up into three different color submatrices, with $A_G=A_d+A_b+A_d$ (where $d$ is dark, damn...). It's ...
0
votes
0answers
12 views

Request: superposition of triangular lattice and its dual graph

Does anyone know where I could find a pdf of graph paper with both the triangular lattice and its dual hexagonal lattice superimposed? I'd like my students to have something they could easily doodle ...