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

Relation between a complete k-partite graph and a perfect graph

Is a complete $k$-partite graph also a perfect graph? I know that the result holds for bipartite graphs. Can we claim the same for higher order partitions?
1
vote
0answers
95 views

Research Topics Needed

This coming academic year a professor has asked me to find some topics that I wish to pursue to write about. The problem/topic that will be discussed doesn't have to be open, but my trouble is that I ...
1
vote
0answers
61 views

Round robin tournament scheduling with additional constraints

I'm looking for a solution to the following problem. Given $n = a\cdot (b-1) + 1$ players, $a$ and $b$ being integers with $a \leq b$, I want to schedule a round-robin tournament where every player ...
1
vote
0answers
47 views

Strongly regular tournament

A digraph on $n$ vertices is called a tournament if there is a exactly one directed edge between any two distinct vertices. A vertex $v$ dominates a vertex $w$ if there is an edge from $v$ to $w$. ...
1
vote
2answers
51 views

For all $1 \leq i < j \leq k$, the subtrees $T_i$ and $T_j$ have a vertex in common. Show that $T$ has a vertex which is in all of the $T_i$.

Can someone please verify my proof or offer suggestions for improvement? I am aware that there is a similar question elsewhere, but I want help with my proof in particular. Let $T_1, \ldots, T_k$ ...
1
vote
0answers
47 views

Find minimum cut corresponding to maximum flow

I am trying to find the minimum cut corresponding to the maximum flow that is given in the following network (the numbers in italic represent flow; the boldfaced numbers represent capacity). I tried ...
1
vote
0answers
31 views

A inequality on a graph and finding the best constant

Find the smallest positive constant $c$ satisfying: For any simple graph $G=G(V,E)$, if $|E|\geq c|V|$, then $G$ contains $2$ cycles with no common vertex, and one of them contains a chord. Note: The ...
1
vote
0answers
58 views

Set partitioning question

I have the following problem. I have $n$ sets $A_1$ to $A_n$ each with $k$ elements. Any two sets are disjoint. I'm looking to determine a second set of $m$ sets $B_1$ to $B_m$ such that: the sets ...
1
vote
0answers
24 views

What, if any, is the name of a k-uniform hypergraph where edges are ordered tuples

Suppose I have a hypergraph where the set of vertices can be partitioned into n subsets with n < k, and edges in this graph are restricted to ordered tuples having some structure imposed relating ...
1
vote
0answers
40 views

Variations of M,n,k-games

I just read about M,n,k-games and wondered if the following variation (with fixed $k$) has been studied as well and if there exists a name for it: Two players consecutively mark elements of ${\bf Z}$ ...
1
vote
0answers
43 views

resilience of graphs question

The following is a definition of the resilience of a graph w.r.t to a property $\mathcal{P}$ (Local resilience) A property $\mathcal{P}$ is said to be monotone if the property is preserved under ...
1
vote
0answers
61 views

Find tree diameter or center

I want to find center in a graph that doesn't have cycles. I heard, that this is how I find a diameter: Take random vertex A Find such vertex B, that distance to it is maximal Find such vertex C, ...
1
vote
0answers
17 views

about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...
1
vote
0answers
90 views

When counting faces in a planar graph - when is each edge counted twice?

So I'm confused even though this is supposed to be simple: From what I understand, in a planar graph, if we count the edges of each face, we should get $\sum F_t \le 2|E|$ because an edge can ...
1
vote
0answers
51 views

What does “total variation on a graph” mean? How can I visualize it?

There is a paper " The Total Variation on Hypergraphs -Learning on Hypergraphs Revisited" which I am reading and I was not able to appreciate the term "total variation" in terms of graph theory. ...
1
vote
1answer
75 views

Prove the number of total dominating sets of a bipartite graph is not exactly divisible by $2$

here is a cute problem I created from another not so cute problem I made from a cute problem. Prove the number of total dominating sets of a bipartite graph is never exactly divisible by $2$ ( of the ...
1
vote
0answers
51 views

Litterature on Dynamic graph theory

I was wondering if anyone knows any good articles or papers or books on graph theory that deals with changing graphs and not just static ones. So far I've only found qualitative descriptions of ...
1
vote
0answers
48 views

Using red/blue algorithm on graph with zero cycle

I have a graph where I am trying to find minimum spanning tree using the red rule, blue rule approach. Now the graph is a directed graph and it has a zero cost cycle near the terminal point. In fact ...
1
vote
1answer
22 views

Name for the type of relation similar to the edge set of a regular directed graph?

For a binary relation over a set, if each member in the set appears the same number of times in the first position and in the second position in the relation, is there a name for such a relation? For ...
1
vote
1answer
29 views

Random graphs question regarding exponents

On page 19 http://www.iecn.u-nancy.fr/~chassain/GDT/documents/SpencerStFlour.pdf All in the first Paragraph. it gives an estimate of (they use equal instead of approximation) ...
1
vote
2answers
95 views

Proving the theorem of graph theory

I want to know the proof of the condition of a Euler walk or tour in a directed graph. I googled a lot about it from MIT courseware to some other YouTube channels but I couldn't find any proof for ...
1
vote
0answers
201 views

Dijkstra Algorithm proof

I was studying the proof of correctness of the Dijkstra's algorithm . In the above slide , $d(u)$ is the shortest path length to explored $u$ and $$\pi(v) = \min_{ e\ =\ u,v:u \in S}d(u) + l_e$$ and ...
1
vote
0answers
67 views

Steiner tree problem in 3D?

Steiner tree problem in the plane (2D) is explained on wiki that though there's no straight solution, the solution has some properties, namely points added to the graph (Steiner points) must have a ...
1
vote
1answer
63 views

Let $G$ be a graph of girth $5$ for which all vertices have degree $\geq d$. Show that $G$ has at least $d^2+1$ vertices.

Could someone verify this? Pick a vertex $v$ of $G$. Pick distinct vertices $u_1, u_2, \ldots, u_d$ incident with $v$. Note that this can be done since $v$ has no loops and degree $\geq d$. For each ...
1
vote
0answers
16 views

Implementing Equation on current data

I am trying to implement Personality, Gender, and Age in the Language of Social Media equation. I have 5 patterns and one list of 100 text = 900 words. The result of find a Match in the 900 to the ...
1
vote
1answer
30 views

Is there notation or a name for the complement of the unbounded face of a planar graph?

Let $G$ be a finite graph embedded in $\mathbb{C}$. Let $F$ denote denote its unbounded face. Is there notation or a name for $F^c$ without referring directly to $F$. Of course this is equivalent ...
1
vote
0answers
56 views

proof for critical graphs

A graph $G=(V,E)$ is said to be critical if for every edge $e$ not in $E$, adding $e$ to $G$ creates a new copy of $K_{10}$. Find a critical graph on $n$ vertices with ${n\choose 2}-{n-8\choose 2}$. ...
1
vote
0answers
49 views

Famous graphs with nice 3D embeddings

The Petersen graph has an interesting 3D embedding. Take a tetrahedron. Add a midpoint to each edge. Connect opposing midpoints for a Petersen graph. The Perkel graph or 57-cell has an interesting ...
1
vote
0answers
21 views

How to observe the evolution of communities in political discussions

I analyse political talks among actors across time. I have a dataset that contains information on who talked to whom and when. I want to model this information into a graph so to apply community ...
1
vote
0answers
24 views

Do the partitions created by a graph cut need to be connected?

I have a question regarding graph cuts in graph theory. Suppose that there exists a graph G and I was to implement a graph cut to partition the vertices in graph G into two subsets A and B. Would the ...
1
vote
0answers
100 views

Reiman theorem in extremal graph theory

I need a source where I can find a proof of the Reiman's thorem: If the graph G is quadrilateral($C_4$)-free, then $$|E(G)| \leq \frac{|V(G)|}{4}(1 + \sqrt{4\cdot|V(G)| - 3})$$ Here is the idea of ...
1
vote
0answers
80 views

3-pass counting triangles algorithm

Hei guys, I need some hints on Counting subgraphs in data streams. Consider this 3-pass counting triangles algorithm: 1st Pass: count the number of edges |E| in the stream 2nd Pass: sample ...
1
vote
0answers
83 views

The Boggle Problem

An open question in mathematics that has yet to be resolved is as follows: given an $N\times N$ boggle grid, how many total simple (non-intersecting, in the sense of not returning to the same node ...
1
vote
1answer
127 views

The shortest path connecting three points

I have 3 points X,Y,Z, lets call them buildings. I need to find the shortest amount of path that connects the 3 buildings, these buildings can be in any sort of shape and any distance from each ...
1
vote
0answers
63 views

Ore's Theorem - Graph Theory

I'm trying to understand Ore's Theorem but it seems I'm a bit confused. "Theorem (Ore; 1960) Let G be a simple graph with n vertices. If $$\operatorname{deg}(v) + \operatorname{deg} (w) ≥ n$$ for ...
1
vote
0answers
50 views

Finding the adjacency matrix for any given quiver and some collection of words.

For a directed graph (quiver) $Q$ with $n$ vertices and without multiple arrows, we have the adjacency matrix $A$, in which $A(i,j)=1$, if there is an arrow from $i$ to $j$, and $0$ elsewhere. This ...
1
vote
0answers
45 views

O(m) all-pairs shortest paths algorithm for directed acylical graph

An exercise I'm working on asks me to devise an $O(m)$ algorithm for the all-pairs shortest paths of the graph $G = (V, A)$, where $(v_i, v_j) \in A$ implies $i < j$. I'm wondering whether this is ...
1
vote
0answers
24 views

Hasse diagram of bool expressions

I know mean of hasse diagram but I don't know algorithm for drawing. For example I have this expression: $x_{1}'x_{2}x_{3}\lor x_{1}x_{2}x_{4}\lor x_{3}x_{4}x_{5}x_{6}$ How to draw hasse diagram of ...
1
vote
1answer
68 views

Showing that a diagram commutes in the most economical way

Suppose that one had to consider (co)cones on a complicated diagram, with many arrows and objects and that one wished to prove that one of them is final/initial. Given another (co)cone, one would ...
1
vote
0answers
43 views

If G compliment is disconnected, then chromatic number = circular chromatic number

I've been reading through a book called graph homomorphism and this is an exercise I've been trying to prove. Here's my work so far Induction on number of vertices Basis : this clearly holds ...
1
vote
0answers
48 views

Flows in signed graphs and coloring

Nowhere-zero flows and coloring of planar graphs are related by duality. (wiki) I heard that there was a similar relation for nowhere-zero flows in signed graphs and colorings of some other graphs. I ...
1
vote
0answers
39 views

Spectrum of an infinite graph independent of labelling

Does there exist an infinite graph whose spectrum does not depend upon the labelling of the graph? While evaluating the spectrum, I am considering adjacency matrix of the infinite graph as a bounded ...
1
vote
0answers
31 views

Directed Hamiltonian Reduction

The reduction function given by Richard Karp in 'Reducibility among combinatorial problems' for Directed Hamiltonian Cycle $\leq_{p}$ Undirected Hamiltonian Cycle goes as follows : for input $G = ...
1
vote
0answers
41 views

how to find a route in a graph

"Dr C is a tourist by nature, and wishes to visit each place once and return to her starting point. Dr D is an explorer, and wishes to traverse every road just once, in either direction; he is ...
1
vote
0answers
84 views

Density of bridges for critical random regular graph

Let $G_{n,d}$ be the space of all $d$-regular graphs with $n$ vertices. Now choose a graph from $G_{n,d}$ uniform at random. Once obtained do independent bond-percolation on it, i.e. keep an edge with ...
1
vote
0answers
32 views

sufficient condition for k-connected

Let $(d_1, d_2, \dots, d_n)$ with $0 \leq d_1 \leq d_2\leq \cdots \leq d_n$ be a degree sequence of a graph $G$ with $n$ vertices. Show that if $d_j \geq j+k$ for all $j \leq n-1-d_{n-k}$. Then $G$ is ...
1
vote
0answers
85 views

Average Degree of a Random Geometric Graph

A set of $N$ points are distributed randomly on a unit square with uniform distribution. Two points $\mathbf{p}_i$ and $\mathbf{p}_j$ are said to be connected if $\|\mathbf{p}_i - \mathbf{p}_j\| \leq ...
1
vote
1answer
41 views

Prove that sub-trees have a common vertex

OK so this is a bonus question I got that I would really like to solve because I have been sitting on it for an hour without any progress. Any direction from you guys would be very helpful: Let $T$ ...
1
vote
0answers
57 views

3-connected graph

Let $G$ be a 3-connected graph. Prove that for every three vertices $a, b, c$ of $G$ there exists a cycle in $G$ that contains $a,b$ but not $c$. Here is my work. Since $G$ is a 3-connected graph, ...
1
vote
1answer
28 views

How many spanning trees of a complete graph with an even number of vertices can be split in half by removing a single edge?

We have a complete Graph G with |V|=n . We know it has n^(n-2) possible spanning trees. How many of them could be split into two equal halves by removing a single edge?