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
21 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 ...
1
vote
0answers
34 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
21 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 ...
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
40 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 ...
0
votes
0answers
40 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.
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 ...
-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
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 ...
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
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
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.) ...
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 ...
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
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 ...
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 ...
3
votes
1answer
47 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 ...
0
votes
0answers
25 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 ...
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 ...
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
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. ...
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
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
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\ ...
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 ...
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 ...
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 ...
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 ...
-1
votes
0answers
19 views

cycle decomposition of graphs

I am trying to find the number of elements in cycle space of a graph G,as I know every even graph has a cycle decomposition,and I wana find the number of cycles in a graph and I think the cardinality ...
1
vote
0answers
17 views

Understanding ILP formulations of combinatorial optimisation problems

I am having trouble understanding and producing integer linear programming formulations for combinatorial optimisation problems. I can understand basic ones like the knapsack problem: $min \quad ...
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 ...
0
votes
2answers
54 views

Every simple graph with no loops and more than one vertex has at least 2 vertices of the same degree.

I've been given the following statement, I need to decide if it's true/false and if true, prove it: Every simple graph with no loops and more than one vertex has at least 2 vertices of the same ...
0
votes
1answer
30 views

Simlpe Loops in Topological Graph

Given a set of points in 3D space, and a set of links between them which form a connected graph - is there a general strategy for extracting all simple loops from such an object? I refer to simple ...
1
vote
1answer
25 views

Anti-symmetric if $AB= 1$ and $BA=0$ but every vertex has loops?

I'm creating a directed graph from an adjacency list. The $0$ present that there is no relation while the $1$ represent that there is. So i have a quick question regarding this. Lets assume that $AB ...
0
votes
0answers
20 views

Number of Crossing Cycles of length $3$ in a complete graph if we put $m$ edges on one side?

Alice and Bob don't play games anymore. Now they study properties of all sorts of graphs together. Alice invented the following task: she takes a complete undirected graph with $n$ vertices, ...
0
votes
1answer
101 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 ...
1
vote
1answer
39 views

A strange scheduling for $K_{24}$.

This question came from a question asked earlier today linked here The question implicitly asked how to make a schedule with his/her class of 24 students such that: 1) Everyday will consist of the ...
1
vote
0answers
40 views

A cubic simple graph without cut edges is matching covered

I recently found the following exercise: Given a cubic, simple undirected graph $G$ without cut edges, then $G$ is matching covered. I.e. every edge is contained in a perfect matching. My idea ...
0
votes
1answer
19 views

Suppose u and v are vertices in G. ecc(u)=m, ecc(v)=n, and m<n. prove d(u,v) is greater than or equal to n-m

I'm having trouble making progress on this. I'm trying to use contradiction and I'm really not seeing anything. Any help would be greatly appreciated!
0
votes
0answers
15 views

Edge-transitivity of Folkman Graph

I need to prove that the Folkman Graph is edge-transitive but not vertex- transitive. I have the second part but I'm stuck with the edge-transitivityi part. Can you give some help? Thanks.
0
votes
1answer
20 views

Are all adjacency matrices (graph theory) diagonalizables?

If $A$ is an adjacency matrix of a graph $G$ and it can be diagonalized to get it in the form $A=PDP^{-1}$, with $D$ diagonal, is there any graph-theoretic interpretation to the matrices $P$ and $D$?
0
votes
1answer
29 views

Lower bound on circuit size of a Boolean function

I'm currently reading a proof of the following claim from the notes http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf which can be found on the bottom of page 6. I'd like to point out i'm interested ...
0
votes
0answers
18 views

Algorithms for finding maximum matching in a graph

I need to learn as much as possible algorithms for finding maximum matching in a graph (directed and undirected, bipartite and non-bipartite). At the moment, I have the following algorithms: ...
0
votes
1answer
23 views

Are all connected graphs with Euler characteristics 2 planar?

I have read proofs and descriptions stating that a planar connected graph have the Euler characteristic 2. I'm not sure if that statement is equivalent to "a connected graph with the Euler ...
1
vote
1answer
23 views

$|A|$,$|B|$, and $|C|$ in a $k$-regular tripartite graph $(A, B, C)$

Let $k>0$ and let $G$ be a $k$-regular tripartite graph with partition $(A, B, C)$. I want to prove that it is not necessary that $|A|=|B|=|C|$. As a counterexample, I constructed the graph shown ...
0
votes
0answers
23 views

Reference for Ramsey Numbers

Just wondering about diagonal Ramsey numbers $R(n)$. Can anyone provide reference on either of the following? Have there been any notable attempts to make sense of $R(n)$ by using non-combinatorial ...
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 ...