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

Edge colorability of small d/k graphs - among the largest known graphs for the undirected degree diameter problem

What is known about the edge colorability of the graphs residing in the small d/k section in this table (upper left corner) ? For example, what is the chromatic index of the d=4, k=4 graph with 41 ...
1
vote
0answers
33 views

To find out the minimum required jumper number between objects

I try to find out the minimum required jumper number for connection between objects. The rule is : all objects are on a plane and need to connect all objects with only one connection. The minimum ...
3
votes
0answers
18 views

$\alpha$-critical graphs and chordless odd cycles

An $\alpha$-critical graph is a graph in which the removal of any edge increases the independence number. Sometimes isolated vertices are forbidden, but that is irrelevant for this question. It is ...
0
votes
0answers
39 views

Worst case for the stable marriage problem

What is the worst case for the stable marriage problem? I know the worst case is $n^2 - 2n + 2$ but I would like to know how to prove it.
0
votes
2answers
19 views

Why are the number of verticies in a clique graph less than its a parent graph [duplicate]

I am reading up about Graph theory and the example it gives for a Clique Subgraph looks like this... Now it states that the bottom graph is "obviously" the clique graph for the top. Is this because ...
3
votes
1answer
46 views

graph partition, second smallest eigenvalue.

In spectral graph partition theory, the eigenvector corresponding to the second smallest eigenvalue of the laplacian matrix of a graph, in general, is used to partition the graph. What is the ...
9
votes
0answers
70 views

What can we say about the graph when many eigenvalues of the Laplacian are equal to 1?

The Laplacian of the graph has all the eigenvalues real and non-negative, the smallest being 0. I have a graph where the second smallest eigenvalue (the so called algebraic connectivity) is equal to ...
1
vote
2answers
26 views

Graph construction terminology

Given graph $G=(V,E)$, is there a graph $H=(U,F)$ where the edges of $H$ are the vertices of $G$ and the vertices of $H$ are the edges of $G$? If $G$ is a complete graph, what is $H$? How do cycles ...
3
votes
0answers
94 views

Transpose of the adjacency matrix

As homework I had to do an adjacency matrix for the following graph: My solution was the following: $$ \begin{bmatrix} 0&0&1&0&0 \\ 1&0&0&1&0 \\ ...
1
vote
0answers
24 views

Independence of Events in Lovasz Local Lemma

Let $G$ be a (finite) graph with maximum degree $d$ and vertices $v_{1}, \dotsc ,v_{n}$. Let us associate an event $A_i$ with $v_i (i = 1, . . . , n)$ and suppose that $A_i$ is independent of the ...
1
vote
1answer
33 views

Raising an adjacency matrix to a power: Why does it work?

An adjacency matrix $M$ represents the number of ways to travel between pairs of points in a network in exactly one move. $M^k$ represents the number of ways to travel between pairs of points in a ...
1
vote
0answers
37 views

$k$ Dimensional Weisfeiler-Lehman Method

I am reading An Optimal Lower Bound on the Number of Variables for Graph Identification (1992) On page 4 , the paper says, The second hope was partly based on the following result of Cameron ...
-1
votes
0answers
9 views

What is the average pathlength to cross any given graph? [on hold]

@ Jedediyah In the answer to the question "... What is the average path length and probability to cross any given graph?...", you have answered that "...Let N be the matrix M with the last row and ...
2
votes
1answer
383 views

Does a closed walk necessarily contain a cycle?

[HOMEWORK] I asked my professor and he said that a counter example would be two nodes, by which the pathw ould go from one node and back. this would be a closed path but does not contain a cycle. But ...
-1
votes
2answers
38 views

Graph with a pendant vertex

I am trying to prove the following statement but cannot make a first step forward. If $G$ is a simple graph in which neighbours of an arbitrarily chosen vertex have different degrees, then $G$ has ...
1
vote
1answer
145 views

Can a method related to “Weisfeiler-Lehman Method” provide better time complexity for Graph Isomorphism than existing result?

Cai-Furer-Immerman showed that the W-L(Weisfeiler-Lehman ) hierarchy cannot distinguish general graphs except at linear dimension. Even besides CFI's result, there is good reason to believe that ...
0
votes
1answer
321 views

3-regular connected planar graph

Let $G$ be a 3-regular connected planar graph with a planar embedding where each face has degree either 4 or 6 and each vertex is incident with exactly one face of degree 4. Determine the number of ...
0
votes
0answers
18 views

Upper limit on Ramsey number $R(a,b)$

How could we prove that if $R(a-1,b)$ and $R(a,b-1)$ are both even then $R(a,b)$ is strictly less than $R(a-1,b)+R(a,b-1)$ or $\begin{equation} R(a,b) < R(a-1,b)+R(a,b-1) \end{equation}$
0
votes
4answers
60 views

Is it possible to find the criminal with graph-theoretic methods?

I've been presented to a problem: Someone commited a crime. When interrogated, the people, named $G,m,M,J,D$ argued: $G:$ It wasn't $D$; It was $M$. $m:$ It wasn't $M$; It wasn't $D$ ...
1
vote
1answer
18 views

Meaning of 3-disjoint

Definition: Two edges $\{x, y\}$ and $\{w, z\}$ of $G$ are said to be 3-disjoint if the induced subgraph of $G$ on $\{x, y, w, z\}$ consists of exactly two disjoint edges. (See page 5 of this file.) ...
0
votes
1answer
32 views

Graphing social connections in a middle school.

Imagine a middle school with the usual assortment of bullies and bullied, popular and lonely, violent and passive, and troubled. I try to keep up on who's doing well and who is not. My data consists ...
0
votes
0answers
13 views

Using graph theory in Wireless sensor network

I am doing my research in wireless sensor network. However, I am very much interested in graph theory too. I am asking this because I cant think any better source than here to answer this. The ...
0
votes
2answers
23 views

If $G$ is a simple, no loops graph, with n vertices and e edges, whose vertices have degree k or k+1 then G has $n_k$ vertices.

Question: Decide if the following expression is true or false. Prove or give a counterexample. If $G$ is a simple, no loops graph, with $n$ vertices and $e$ edges, whose vertices have degree ...
2
votes
1answer
75 views

Does an Eulerian semi-graceful polyhedral graph exist?

In a graceful graph, the vertices have number values that range from 0 to $n$ and $n$ edges with all values from 1 to $n$ that are differences between the vertex values. Here's a graceful but boring ...
11
votes
2answers
163 views

Islands game and graph theory

I'm trying to recreate an electronic version of the game Hashiwokakero shown below:   →   Images by Wikipedia user Val42, used under the CC-By-SA 3.0 license. The game is ...
3
votes
0answers
44 views
+50

Bounding 2nd-smallest eigenvalue of the Laplacian of the binary tree

I am reading on my own the notes of this lecture series from 2012: http://www.cs.yale.edu/homes/spielman/561/2012/lect04-12.pdf. In section 4.7.2 (page 8) it's mentioned that we can prove a lower ...
4
votes
1answer
442 views

Why does my Barabasi Albert model implementation doesn't produce a scale free network

I'm trying to implement the Barabasi Albert model to generate some scale free network matching a power law distribution of degree. I'm using a value $m = 2$ for the main parameter of the algorithm, ...
3
votes
2answers
30 views

Ergodic components of Markov chain by transition matrix

I would like to find an algorithm for obtaining all ergodic components of a finite Markov chain with discrete time defined by its transition matrix (i.e. ergodic subchains into which the given chain ...
2
votes
1answer
38 views

Paths starting from a given node that touch each node a given number of times

How many paths starting from a given node touch each node a given number of times? We have a complete graph with vertices $1,2,3…j$. We want to know the number of paths of length $N$, starting from ...
4
votes
1answer
94 views

The Adjacency Matrix of Symmetric Differences of any Subset of Faces has an Eigenvalue of $2$…?

Assume a cubic (for the bounty) planar graph $G$ and let's call its faces $f_k\in F$. The adjacency matrix of any face $f_k$ has an eigenvalue of $2$, since it's a $2$-regular graph, i.e. a cycle. I ...
-1
votes
1answer
32 views

Trivial Graph theory questions [on hold]

Can every disconnected graph be decomposed into 2 disjoint subgraphs ? If yes then edge-disjoint or vertex-disjoint ? and Why ? If not then what are the exceptions ? Given n vertices is it always ...
4
votes
1answer
54 views

Polynomial algorithm for problem in graphs which can also be solved as a linear programming problem.

I have an (undirected) graph $G = (V, E)$. For each vertex $i \in V$ we have a cost associated $v_i$ and for each edge $e \in E$ we have a prize associated $x_e$. My problem is to find $W \subseteq ...
2
votes
1answer
25 views

Can CNF Hamiltonian graphs be turned to “DNF” graphs?

Given a CNF SAT formula, we can turn it into a Hamiltonian graph, which is Hamiltonian iff the formula is satisfiable. Now, we can transform the CNF formula into a DNF one. My question is, can the ...
2
votes
2answers
291 views

Finding characteristic polynomial of adjacency matrix

Short question im having a tad difficulty with. I'm trying to find the characteristic polynomial of a graph that is just a circle with n vertices and n edges. I think the adjacency matrix should ...
4
votes
0answers
42 views
+50

Configurations of eleven (or more) points in the Euclidean plane, such that out of any four there is a pair at unit distance.

Inspired by this question, I was wondering the following: What is the maximal size of a subset $C$ of the Euclidean plane such that out of any four points in $C$ there are two at unit distance ...
0
votes
1answer
100 views

Is there a term called 'GRAIL'?

I've been a talk with a PhD student about some graph issue and told me about GRAIL graph and have drawn it for me as you see in the picture, however, I try to generalize so-called "Grail graph" to ...
2
votes
1answer
42 views

Find edge disjoint spanning tree subgraph between A and B

Given an undirected graph G(V,E). A and B are elements of V. Identify a subgraph of G containing A & B with 2 edge disjoint spanning trees (or prove one doesn't exist). I have found several ...
0
votes
0answers
24 views

Conjecture on different type of triangle in a complete graph?

How many different triangles are there in $K_5$? The Answer is 35.(The Moscow Mathematics Puzzle) Then I asked what about $K_6$, $K_7$ and so on ...? With my intuition I arrived at this ...
1
vote
1answer
28 views

Construct a digraph which reflect four given rankings and use component analysis to interpret these rankings

Suppose that four judges $J_1$, $J_2$, $J_3$, and $J_4$ each rank eight objects: $O_1,O_2,\ldots,O_8$ independently. Their rankings are $$\begin{array}{cc} J_1: & O_1\ O_2\ O_3\ O_4\ O_5\ ...
0
votes
4answers
38 views

If $G$ is a simple, connected graph with no loops or cycles, then it has at least two vertices with degree 1.

Question: Prove the statement: If $G$ is a connected graph with no cycles, then it has at least two vertices with degree 1. This seems pretty obvious, as if the graph has no cycles then it ...
2
votes
1answer
29 views

The upwardly closed subgraph

I'm reading the book Probabilistic Graphical Models (Koller and Friedamn). I'm not quite sure about this example: Given the next graph: The updwardly closed subgraph K+[C] is: I don't get it. I ...
0
votes
2answers
23 views

Finding isomorphism classes of graphs, given $|V|, |E|$, degree sequence, etc.

In this particular question I'm asked to find all the isomorphism classes of simple graphs, without loops whose degree sequence is: $3,3,2,2,2$, and to prove the ones I found are all the ones that ...
1
vote
1answer
33 views

Genus and faces of a graph

I am trying to determine the genus of a simple, undirected, connected graph using Euler's formula. However, I'm having trouble computing the number of faces of this graph: I seem to be confused ...
1
vote
1answer
17 views

Given $G_n$, a graph with $2^n$ vertices, show $G_4\simeq Q_4$.

Let $G_n$ denote the $2^n$ vertices graph in which every vertex is labeled with a string of $n$ bits. A pair of vertices are adjacent if and only if their bit strings differ in exactly 3 digits. ...
0
votes
0answers
16 views

Existence of an $x,U$-fan in a $k$-connected graph

Let $G$ be a $k$-connected graph. An $x,U$-fan is a set $U\subseteq V(G)$ of size $|U|\ge k$ together with a vertex $x\in V(G)\backslash U$ and a set of disjoint $x,U$-paths whose only common vertex ...
1
vote
2answers
289 views

Give an algorithm that computes a fair driving schedule for all people in a carpool over $d$ days

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none ...
3
votes
0answers
15 views

How to perturb an adjacecny matrix in order to have the highest increase in spectral radius?

Let's suppose I have a generic directed graph $G$ and it's adjacency matrix $A$. I can add an arc wherever I want in the graph. (i.e. perturb the matrix A changing a single 0 into a 1). Where should ...
3
votes
2answers
3k views

Graph Path Length Problem

Let $G$ be a graph such that $\delta(G) \geq k$. Prove that $G$ has a path of length at least $k$. Solution: We know that $\delta(G) = \min\lbrace \deg(v) \mid v \in V(G) \rbrace$ If $\delta(G) ...
1
vote
1answer
841 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
0
votes
1answer
26 views

Optimal partitioning of a planar graph

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I ...