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

2
votes
1answer
47 views

Proof completion: Determine a simple expression for $\tau(G)$ in terms of the vertex degrees of $G$. (details inside)

I need some help completing a proof I wrote (or seeing a simpler solution to the same problem). For a list of paths $P_1, \ldots , P_m$, let $L(P_1, \ldots, P_m)$ be the number of paths in $P_1, ...
2
votes
1answer
21 views

Prove that there is an edge $e' \in E(T')-E(T)$ such that $T'+e-e'$ and $T-e+e'$ are both spanning trees of $G$.

Can someone please verify my proof or offer suggestions for improvement? Let $T, T'$ be two spanning trees of a connected graph $G$. For $e \in E(T)-E(T')$, prove that there is an edge $e' \in ...
3
votes
0answers
48 views

What is the number of labeled caterpillars?

A caterpillar is a tree in which all the vertices are within a distance 1 of a central path. (See the Wikipedia article: Caterpillar tree, for an example and some equivalent characterizations). The ...
0
votes
1answer
29 views

Show that a finite regular bipartite graph has a perfect matching

Some preliminaries: A matching in a bipartite graph with vertex set $X \cup Y$ is a subset $E_1$ of the edge set such that no vertex is incident with more than one edge in $E_1$ A complete matching ...
0
votes
0answers
21 views

Threshold function for component of size $k$

Show that, for each fixed $k$, there is a function $p(n)$ such that the probability that $G(n,p(n))$ has a component of size exactly $k$ tends to $1$ as $n \rightarrow \infty$. My initial thoughts are ...
0
votes
1answer
50 views

what is the significance of the inverse of an adjacency matrix?

Suppose I have a graph and I calculate the eigenvalues of the adjacency matrix and find that there are some number of zero eigenvalues. Do zero eigenvalues have any significance? Also is there a good ...
0
votes
1answer
29 views

Why doesn't the Back and Forth Method for Infinite Random Grap use the Axiom of Choice?

A way to proof that any two Rado graphs (countably infinite nodes, has graph extension property) are isomorphic, is to use the back and forth method. At each step of the method, we have a vertex $v$ ...
1
vote
0answers
56 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
40 views

Edge choosability(edge list coloring) of cycles

I have 2 cycles with 6 length as shown below. I want to show that the above graph is 4-edge-choosable. I don't know where to start. It's known that every cycle of even length is 2-edge-choosable, ...
1
vote
0answers
16 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 ...
22
votes
1answer
406 views

Zombie outbreak on a $k$-regular graph

Suppose we have a zombie outbreak on a connected $k$-regular graph of order $n$. There are $n_0$ initially infected zombie nodes, and each turn, each zombie infects its neighbors with probability ...
3
votes
0answers
30 views

Diameter of undirected graph

Let $G$ be a strongly connected directed graph of diameter $D$, and suppose that we remove the orientation of the arcs, thus getting an undirected graph $G'$ with diameter $D'$. Obviously, $D' \leq ...
0
votes
0answers
39 views

How to show a total order is product order

Besides the definition of product order, is there any other way to show that a total order on two sets can induce a product order? Because I want to solve the problem below: For two graphs ...
1
vote
0answers
36 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}$ ...
0
votes
1answer
15 views

Differnce between circuits in graphs

Given a full undirected graph with 3 vertices: $v1, v2, v3$ and $3$ edges. Is there any differnce between those 2 cycles: $C1: v1-{(e1)}-v2-{(e2)}-v3-{(e3)}-v1$ $C2: ...
2
votes
0answers
31 views

Probability that half the nodes has more than half out-degree

This is something I just wondered about, and I don't know whether there is a closed-form answer or not. I've tried but without making progress, so any idea would be helpful. Consider a complete graph ...
1
vote
0answers
29 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 ...
0
votes
1answer
23 views

graphs that are both eulerian path and circle / eulerian circle and hamiltonian circle

if G is an Eulerian graph (which means it has Eulerian circle), and G also has an Eulerian path which is not a circle there's not such graph right? for Eulerian circle all vertex degree must be an ...
1
vote
0answers
31 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
25 views

Splitting a graph into two isomorphic parts

Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...
0
votes
1answer
33 views

Distance Transitive Graph Property

Asked this over in math overflow and have refined the question a bit. I'm working on trying to show this, but can't seem to get a proof methodology worked out. No guarantees that it is true, but ...
0
votes
0answers
58 views

2 player team knowing maximum moves

Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know. And also find out how ...
2
votes
3answers
236 views

Combinatorial optimization - Bijections between duplicated numbers

English is not my native language: sorry for my mistakes. Thank you in advance for your answers. Two Bijections and an Array... Here is a 2D array (in this particular example: rows: 1 to 4; ...
0
votes
2answers
32 views

In Dijkstra algorithm, it takes the source, what about the sink?

I'm studying the Dijkstra algorithm, but in my book, the algorithm takes as input only the graph and the source. Why it doesn't ask for the destination vertex? How can it work? Thanks a lot.
1
vote
1answer
43 views

What is the role of induction in the proof of König's Lemma?

I am looking at this version of König's Lemma: let $T$ be a tree with countably infinite nodes, and each node has finite degree. Then, $T$ has a simple path containing countably infinite number of ...
4
votes
1answer
106 views

Category theory for graph theory research

I am doing research in algebraic graph theory, focusing on the relation between graphs and groups (especially the representing groups as graphs) for my Ph.D. In particular, one of the ideas is to ...
0
votes
1answer
42 views

3-regular planar graph

Yet another question I was going over and struggled. Given a 3-regular connected planar graph, so that every vertex lies on the edge of a face of length 4, of a face of length 6 and of a face of ...
0
votes
1answer
26 views

Distinguishing between two sets of tournament partition

A "tournament" is a complete graph such that each edge is directed one way or the other (but not both). Does there exist a tournament of size $2n$ such that we can partition it into two sets $A,B$, ...
0
votes
1answer
18 views

What are the rules for plotting directed graphs?

Say I have an ordered pair of sets. One contains the vertices and the other - edges. What are the rules for actually plotting the graphs with these givens? Can a graph be plotted differently given ...
1
vote
3answers
68 views

Does a path can be Hamiltonian and Eulerian at the same time?

If so does it force it to be a simple circle? Or any other restrictions? How would it look like? Thanks in advance
2
votes
2answers
23 views

Is there a name for this type of graphs?

From a graph G I want to construct a graph (lets call it) G# with the following properties: Each node and each edge of G is a node of G# For each e in G connecting the nodes n1, n2 there exist the ...
0
votes
0answers
36 views

Proving properties of Random Graphs

I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas. Consider the random graph model $G_{n,p}$ where its ...
2
votes
0answers
15 views

Sampling from a graph

Suppose you have a graph $G=(V,E)$ that is unobservable globally and you wish to take a sample from the vertices of that graph to infer something about its global properties from local properties. ...
0
votes
0answers
19 views

$k$ edge-disjoint $r$-arborescences in an acylic digraph

An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$. I would like to prove the following: I have thought ...
0
votes
1answer
37 views

Checking the correctness of the adjacency matrix for the given graph

I found the adjacency matrix for this graph; it is shown next to it. Is it correct?
0
votes
1answer
27 views

Proving any N x M undirected two dimensional grid is bipartite

I am trying to self learn graph theory basics by myself, and it would be really helpful is somebody could double check one of my answers: Let $N$ and $M$ be positive integers. Show that any $N$ x ...
0
votes
0answers
9 views

Average time to split a square lattice under random edge deletions

Suppose one successively deletes uniform at random edges from the square lattice with periodic boundary conditions and $L\times L$ sites. How many steps, in average, are necessary to create a second ...
5
votes
1answer
89 views

What is the name of a graph made of k copies of a 4-cycle connected end to end in a chain, possibly with leaves?

Do graphs of the following sort have a specific name? We've been calling them Cactapillars, as they're cacti that look a little like caterpillars (and the name Caterpillar already refers to a ...
2
votes
0answers
28 views

Is there a bound for the genus of the generalized petersen graphs?

I've looked online and could only find a bound for specific generalized petersen graphs. Does any bound (lower or upper) depending on $n$ and $k$, where $n$ is the order of a cycle and $k$ is the ...
3
votes
0answers
67 views

A game on a smaller graph

In this question Alice and Bob play a game on $K_{2014}$, Alice directing one edge, Bob directing $1$ to $1000$ edges with Alice trying to make a cycle. The proof that Alice can win depended on the ...
2
votes
3answers
34 views

Prove that if a $k$-regular bipartite graph has a bipartition $(x,y)$ then $\vert x\vert=\vert y \vert$

A problem I don't know how to attack... a bipartite is supposed to have one end in $x$ and one in $y$. A graph is $k$-regular if $d(v)=k$ for all $v\in v(G)$
0
votes
1answer
40 views

Proof that a graph is 5-colorable

So I had an exam today and one of the questions were: G is an undirected graph, and every two of its odd-lengthed cycles have a common vertex. Prove that G is 5-colorable. So I found this answer ...
1
vote
2answers
50 views

Prove that a complement graph of a tree is either connected or it's a union of an isolated vertex and a full graph

I managed to prove the second part - that a tree that is one vertex with n-1 degree and all the rest are connected to it - the complement graph of such tree is an isolated vertex and the rest of the ...
0
votes
1answer
31 views

I need to understand bipartite graphs

Hi i didnt find good information on the web about bipartite graps. For example does the sum of the degrees on both sides have to be equal? or a bipartite graph G (with side A & B) whose number of ...
0
votes
1answer
32 views

Is it allowed to draw multiple loops in not simple graph?

I mean multiple loops on the same node for example can I have a graph whose degree level is 6 and it contains only one node?
2
votes
1answer
31 views

Thickness of $K_{5,5}$

How to compute the thickness of $K_{5,5}$? By Euler formula it is greater than 1, and 3 is constructible($K_{2,5}*3$), but how to prove it is not 2?
0
votes
1answer
25 views

No minimal imperfect graph of order 200

Prove that there is no minimal imperfect graph of order 200, without using the Strong Perfect Graph Theorem.
0
votes
0answers
32 views

A planar graph has either 2 faces or 2 vertices of degree less than 3

Practicing for an upcoming test, I stumbled upon this question: A planar graph with at least three vertices has either 2 faces of length at most 3, or 2 vertices of degree at most 3. Which is a ...
2
votes
1answer
39 views

What is the realization of a graph in $\mathbb{R}^d$?

I am an undergraduate who has been overhearing students talking about realizations of graphs in $\mathbb{R}^d$, and I am curious to know what that means. To be honest, I don't even know what a ...
3
votes
0answers
36 views

An undirected graph $G$ can be decomposed into simple edge-disjoint cycles if and only if all of its vertices have even degree.

Research effort: $\rightarrow)$ I think this is relatively easy. $\leftarrow)$ Let $G = (V,E)$, let $w$ be any vertex of $G$, given that all the vertex have even degree, I'm assured that I can ...