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

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

Is there a term in graph theory 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 ...
1
vote
0answers
39 views

Eigenvectors of graph laplacian

Let $L$ be the laplacian matrix of a graph $G$, i.e. $L = D - A$, where $D$ is the degree matrix, and $A$ the adjacency matrix. Let $v_i$ be an eigenvector of $L$. Let $x,y$ be two vertices of the ...
1
vote
1answer
150 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 ...
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 ...
0
votes
1answer
32 views

Paths in a finite graph

If we use the standard definition of a path in a graph, is it possible that there exists an infinite path in a finite graph?
3
votes
0answers
123 views

What kind of graph/group theoretical structure is that?

Think of a simple cubic planar graph G with no triangles (let's call the set of such graphs plus the empty graph, [G]). Now pick a vertex and remove it and all its edges. You're left with a graph ...
3
votes
1answer
51 views

Given a graph G, if X(G) = k, and G is not complete, must we have a k-colouring with two vertices distance 2 that have the same colour?

As the title asks, If given a graph, G, with chromatic number k, and G is not complete must there exist a k-colouring of G, f, where there are two vertices x,y such that d(x,y) =2 and f(x) = f(y). ...
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 ...
4
votes
0answers
47 views

Ramsey number $R(K_4,K_4,K_4)$.

I've done a bit of googling, but I can't seem to locate any bounds for $R(4,4,4)$. Here, $R(n_1,n_2,n_3)$ is the generalized Ramsey number where $n_1,n_2,n_3$ are orders of complete graphs. So, in ...
2
votes
1answer
32 views

Stable marriage problem with all men having the same preference

Does a Stable marriage matching exist when all men have the same preferences for women, but the women do not have the same preferences when it comes to men? One example case is: Man 1 pref.: Woman 1, ...
0
votes
1answer
18 views

The number of 5-vertex Hamiltonian graphs

I have to find numbers of 5-vertex Hamiltonian graphs to the nearest isomorphism. I found 9 of them but the answer is 8. I can't find the wrong one, maybe the answer is wrong? Those are my graphs: ...
5
votes
1answer
139 views

The locker puzzle - predetermined strategy

The question is related to the famous locker puzzle: The director of a prison offers 100 prisoners on death row, which are numbered from 1 to 100, a last chance. In a room there is a cupboard with ...
0
votes
0answers
22 views

Minimum vertex cover of two edge disjoint perfect graphs

How well can the minimum vertex cover of the union of a perfect graph and bipartite graph (the two graphs are edge disjoint but not vertex disjoint) be approximated?
0
votes
0answers
42 views

Find the shortest cycle in a directed weighted graph using Dijkstra's algorithm

I was studying Dijkstra's algorithm to find the shortest path from a node to other nodes, and it came out a problem: find the shortest cycle in a directed weighted graph containing a node. I have ...
0
votes
1answer
32 views

Find a recurrence to count paths in a directed graph

Suppose we have an unweighted directed graph with vertices numbered as $1...n$ From each vertex $i$ there are edges to $i+1$, $i+2$ and $i+7$. My task is to find a recurrence $f(i,j)$ to compute the ...
-8
votes
2answers
108 views

Is this map proof that Four Color Theorem is wrong, or I'm missing something? [closed]

Yesterday, after hours of trying I developed one map for which I could not find solution with 4 colors, so I opened topic to ask is there solution for map, and it turned out, there was been solution(I ...
-5
votes
2answers
60 views

prove that every tree is bipartite? [closed]

How can I prove using induction that every tree n>2 is bipartite?
2
votes
1answer
72 views

How many subgraphs does $K_5$ have? [closed]

How many subgraphs does $K_5$ have and how can we prove the result is correct?
-1
votes
3answers
177 views

Four color theorem, What did I miss?

I am not saying that I have proven Four color theorem to be wrong, either I am saying that four-color theorem is wrong but I got one idea so I want to know what I am missing ( This is not proffesional ...
-1
votes
0answers
60 views

Algorithm for seating people in an office [closed]

We recently moved to a beautiful, new office and are now in the process of finalising who gets which room. I am wondering if there is an efficient matching algorithm, which will be of help to us. Let ...
0
votes
0answers
16 views

How many nodes in a K-ary tree with L leaf nodes

Assuming that we have a k-ary tree with L leaf nodes, can the average number of nodes in the tree be calculated if we were to know the average number of children for each node? If not, what other ...
0
votes
1answer
25 views

Dijkstra’s algorithm / path is this done correctly?

im doing this assignment and it seems as if my teacher has made a mistake. according to me in order to find the minimum spanning treee from a-z , you start from a and then go to : a,f,d,c,b,e,z,g ...
1
vote
0answers
14 views

Minimum vertex cover of vertex disjoint odd holes and antiholes

I am interested in knowing whether the minimum vertex cover of a graph that can be written as the union of vertex-disjoint odd holes and odd antiholes can be found exactly, in polynomial time. I could ...
-1
votes
2answers
22 views

Confusion with the reconstruction conjecture?

After reading about the reconstruction conjecture for graphs, I came up with what I thought was a proof by contradiction. Consider the class $T$ of (isomorphism classes of) finite graphs, and the ...
7
votes
0answers
69 views

Share the beer fairly in a finite number of pours

A classical problem within measurements is that you have a $8\,\text{dl}$ mug of delicious expensive beer and need to share it evenly with your friend. However you only have two empty glasses of ...
12
votes
5answers
845 views

How to show these two graphs are not isomorphic?

In my class they gave me some necessary conditions for two graphs to be isomorphic, these two graphs satisfy all of them but I don't think they're isomorphic: Degree sequences are equal. Same amount ...
1
vote
1answer
61 views

Can this expression: $\left \lfloor \left(\frac x 2 \right)^2\right \rfloor $ be rewritten without the floor part?

I was working on a graph theory problem that asks the maximum amount of edges on a bipartite graph of $x$ vertices, I got to the conclusion it should be: $$\left \lfloor \left(\frac x 2 ...
0
votes
1answer
27 views

Map one graph to another graph

consider we have a flow network $G = \{V_g, E_g\}$ and an undirected graph $T = \{V_t, E_t\}$. Nodes of the network G have weights $w(v): v \in V_g$ and edges G have weights $w(u,v): u,v \in E$. Nodes ...
0
votes
1answer
26 views

How do I approach on proving the following fact - 1. Every path is Bipartite?

I am new to Graph Theory. I have sufficient background in Linear Algebra. I found the question in the first exercise of 'Graph Theory' by Bondy and Murty.
0
votes
0answers
39 views

Relationship between the girth of a graph and the number of edges

I'm wondering if there is a relationship between the girth of a simple undirected graph and its number of edges. In particular, given an $n$-node graph $G$ with girth $g\ge 3$, is there an example ...
1
vote
0answers
20 views

Finding locally and globally closing loops in a graph with toroidal topology

I have a two dimensional square lattice (with periodic boundary) with loops on it, i.e., collections of connected links which form closed loops. The lattice has the topology of a 2-torus and therefore ...
1
vote
0answers
27 views

How can I find the longest simple circuit in $K_n$? [duplicate]

How can I find the longest simple circuit in $K_n$? Is there a simple formula that exists?
1
vote
1answer
18 views

Can I make the following assumptions about the longest simple circuits?

The longest simple circuit in $W_n$ is $\frac{3}{2}n$ when $n$ is even and $\frac{3}{2}(n-1) + 1$ when $n$ is odd. I drew it out for a couple of graphs and it seemed to work. Can someone confirm ...
0
votes
0answers
19 views

Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)−d(v)?

This is MCQ of a competitive exam (GATE) , answer is option (d) given by GATE . I found explanation for (d) . With the commonsense or guessing the will be option (d) generally , I have doubt "Is given ...
0
votes
1answer
27 views

How do you find an odd hole in a graph?

Why is there no literature on finding odd holes in a general undirected graph? I found this paper that seems to enumerate ALL chordless cycles (http://arxiv.org/pdf/1309.1051v4.pdf) but apparently, I ...
0
votes
1answer
23 views

Bayesian network query

I am having a bit of trouble with something that I imagine is fairly easy. I am wondering how to get the probability of alarm, JohnCalls, and MaryCalls if they have no prior knowledge of their ...
0
votes
0answers
6 views

Example of weighted max cut taking exponential time iwth local search

In the Coursera algorithms course, the instructor mentions some graphs with weighted edges take exponential time to solve in the worst case with local search the max cut problem. The search algorithm ...