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

Identity for sum of squares of vertex degrees in graph

I am trying to understand this identity but I don't see how they count the same thing: Given a graph $G$ \begin{align*} \sum_{x \in V(G)} d(x)^2 = \sum_{xy \in E(G)} d(x) + d(y) \end{align*} I am ...
0
votes
0answers
11 views

number of edges to build all hamiltonian paths in complete digraph

I'd like to compute the number of edges necessary to build all Hamiltonian paths in a complete digraph. My thoughts so far: Let $N$ be the number of nodes. number of Hamiltonian paths: $N!$ ...
0
votes
0answers
28 views

Minimum cost linear programming problem formulation

I need to formulate a graph and a linear programming problem, and provide a basic solution for the following problem: A singer who lives in city A wants to plan a tour and end it in city E. The ...
0
votes
0answers
19 views

Hamiltonian Ore Property Proof Clarification

If G has order $n \ge 3$ and for all pairs of distinct vertices $x$ and $y$ that are not adjacent, $deg(x)+deg(y) \ge n$ then the graph is Hamiltonian. Here is an image of the proof- I'm hoping for ...
0
votes
1answer
13 views

Hamiltonian Ore Property Proof, why must be connected?

If G has order $n \ge 3$ and for all pairs of distinct vertices $x$ and $y$ that are not adjacent, $deg(x)+deg(y) \ge n$ then the graph is Hamiltonian. Here is the beginning of the proof: We ...
0
votes
1answer
20 views

can we find a $k_4$ colored with 1 color in a $k_8$ which is colored with just 2 colors?

Assume that we define edge coloring in this way : An edge coloring of a graph is an assignment of "colors" to the edges of the graph. So, now imagine we have a $K_8$ which has edges colored with just ...
1
vote
0answers
21 views

Prove that a connected graph with $n$ vertices is a tree iff it has $n-1$ edges. [duplicate]

What are different ways of proving this theorem, using different definitions for a tree (e.g. maximally acyclic graph, minimally connected graph, there's a unique path between any two vertices, etc.)
1
vote
0answers
19 views

Abstract dual of a graph and $K_{3,3}$

Let $G$ be a graph. The abstract dual of $G$ can be defined as a graph $G^*$ whose edges are in one to one correspondence with $G$ and whose spanning trees are obtained by taking the complements of ...
0
votes
1answer
17 views

Existence of hypergraphs with large parameter values

By a result of Erdös, proved using the probabilistic method, there exist graphs of arbitrarily large chromatic number and girth. What are the corresponding results for hypergraphs (given some ...
1
vote
2answers
38 views

Guide to solving Harary's exercises

Most of Harary's harder exercises are research problems (although solved), that need almost always a single key idea as a breakthrough. Often it so happens that even after thinking for a long time no ...
2
votes
1answer
13 views

How are vertices connected in a Johnson graph?

I understand the vertices of a Johnson graph are a k-element subset of an n-element set. Example: N = 4, K = 2 $\left(\frac{4}{2}\right)$ = 6 The 6 vertices are: ...
2
votes
1answer
29 views

Find the expected number of edges in the graph.

It is given that we have a graph with n nodes labelled $\left\{1,2,...,n \right\} $. For each pair of nodes $\left(i\neq j\right)$ , A fair coin is tossed to decide if there should be an edge ...
1
vote
0answers
30 views
+50

Why graph factorization problems emphasize $k$-regular graphs

When we study graph factorization a lot of emphasis is placed on $k$-factorable graphs, i.e. graphs in which the factors are all $k$-regular. Why is such a factorization more important then say ...
1
vote
2answers
25 views

Meeting People at a Party Hamiltonian Graph

Ten people came to my party. Each person meets at least 6 other people, except for my friend Ben who only meets four people. We make a graph H where each person is represented by a vertex, and put an ...
1
vote
1answer
42 views

Stable Matching Problem Worst Preference?

Suppose we have one hundred pairs of women and men, and there is a man M that is ranked the second highest on every woman's preference rankings. Would it be possible that he ends up with the woman he ...
-1
votes
0answers
30 views

How many r-regular graphs of order 6?

How many r-regular graphs are of order 6? Is there an existing graph(s) when our $r{\ge}4$ in r-regular?
13
votes
0answers
88 views

Is there an efficient algorithm for this vertex cycle cover problem? [migrated]

I've been trying to find an algorithm to find a maximum vertex cycle cover of a directed graph $G$ — that is, a set of disjoint cycles which contain all the vertices in $G$, with as many cycles as ...
-4
votes
1answer
28 views

Prove that the shortest path between two vertices in a weighted graph does not change if we multiply weights with the same number [closed]

I need help to prove that if we multiply weights with the same positive number , in a weighted graph, the shortest path between two vertices does not change.
0
votes
0answers
18 views

Why in 2-SAT problem we should make 2-closes instead one?

We know that The 2-SAT Problem is: a problem to decide whether a formula Z on the form CNF with m number of clauses and in each clause 2 variable. and it is a problem in P, because we can represent ...
-1
votes
1answer
33 views

Is there a graph with these properties?3

Is there a way to make a graph with these properties: $i)$ $17$ vertices so that every vertex has a degree of $3$ and $ii)$ $27$ vertices split into two columns where the first column has $10$ ...
0
votes
0answers
33 views

Characterization of non-isomorphic graphs but isomorphic total graphs?

Given a graph $G$, the total graph of $G$, denoted $T(G)$, is the graph with vertex set $V(G) \cup E(G)$, where $a$ and $b$ are adjacent in $T(G)$ if and only if they are adjacent or incident in $G$. ...
0
votes
1answer
37 views

Proof of non-existence simple graph

How can we prove the non-existence of any simple graph with 12 vertices and 28 edges, while at the same time degree of all vertices is 3 or 6?
0
votes
0answers
16 views

Research in Graph Theory and Algorithms in France [closed]

Please recommend me some French Universities where active research is going in Graph Theory and algorithms. If it is possible to get the name of the professor who are working in this field.
0
votes
0answers
13 views

How to prove that finding maximum Independent Set is in P in interval graph?

I have the following algorithm, and I know it returns the maximal independent set. But I don't know how to prove it returns also a maximum IS. 1- Sort all starting point in the interval W. 2- ...
0
votes
1answer
24 views

Are the following families of sets closed under intersection?

Problem Statement Let $X$ be any set whatsoever, and let $f:X\to X$ be any function. Note that in general, no structure is imposed on $f$ whatsoever (i.e. continuity, linearity, etc). The problem is ...
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
24 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
36 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
24 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
29 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
73 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
21 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
62 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
13 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 ...