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

How to find a maximum matching in this graph

Let's consider this graph: Now I take a matching M that only contains the edge 1. Clearly this matching is not maximum, because I can take the edge 3, so given that: We can easily notice that ...
0
votes
0answers
26 views

Does a $K_n$ with $n$ pendants have a name?

Consider the graph we get by taking the complete graph on $n$ vertices, and then attaching a pendant vertex to each of the $n$ vertices by an edge. Does such a graph have a name, i.e. do such graphs ...
-1
votes
1answer
54 views

How to count the number of walks from $u$ to $v$ in a graph?

How can we count the number of walks on a graph from $u$ to $v$? Don't use : If $A$ is the adjacency matrix of the graph, then the $i,j$-entry of $A^n$ is the number of walks from vertex $i$ to ...
-3
votes
0answers
27 views

SimRank Example? [on hold]

By using Similarity in SimRank as shown by this formula $$ s(u,v)= \left(\frac{C}{|I(u)||I(v)|}\right). \sum_{x\in I(u) } \sum_{y\in I(v) }s(x,y) $$ How can we find SimRank between 5,4 ? or s(5,4), ...
0
votes
3answers
31 views

The difference between subgraph and component

I'm studying graph theory right now. I've been reading the textbook and searching the internet, but I still can't understand how subgraph and component are different. Aren't they basically referring ...
-3
votes
0answers
15 views

Let $G$ be a simple graph that is not a forest and has girth $\ge 5$. Prove that the complement of $G$ is Hamiltonian [on hold]

Let $G$ be a simple graph that is not a forest and has girth with length of at least $5$. Prove that the complement of $G$ is Hamiltonian. (girth is the length of the shortest cycle of the graph)
2
votes
0answers
27 views

Counting Spanning Trees Needed to cover Edges

This is in the same spirit as this stackexchange post, but I am seeking a more general answer. The goal is, given a graph $G$, give a method of counting the minimum number of spanning trees needed ...
3
votes
1answer
19 views

How to prove vertex-transitivity in regular graphs.

I have problems to prove wheter a regular graph is vertex-transitive or not. For instance, consider the following examples: the generalized Petersen graphs $P_{2,7},\;P_{3,8}$ and the Folkman graph. ...
0
votes
1answer
23 views

Ratio of degrees of nodes in Graph

I have a question regarding to graph and ratio of degrees of nodes in graphs. See the following image: I'm going to find a relation between $A$ and $C$. So, I count all links from $C$ to $B$s $= ...
1
vote
1answer
25 views

Probability of dominating set in random balanced tournament

I'm trying to estimate some probability in a random tournament, and I know that what I have is false, as it leads to contradicting results published some 40 years ago. But I don't know where the ...
2
votes
1answer
26 views

How to answer this graph theory question?

Okay so let me define some terms before I ask my problem: Let $K_n$ denote the complete graph on $n$ vertices with $n\geq 2$ and let $C_3$ be a cycle of length $3$ (a triangle). Suppose $x,y,z$ ...
0
votes
0answers
25 views

A little bit more difficult problem regarding rooted plane trees

A question regarding rooted plane trees bothers me. We know that the number of rooted plane trees with $n$ nodes equals to $n-{th}$ Catalan number, that is $|Tn| = Cn$. But what is this number if we ...
0
votes
2answers
36 views

Computing expectation exercises; using linearity of expectation and iterator random variables

Disclaimer: This is homework that is overdue by, but I do want to understand it and get through it, so any hints or guidance is appreciated This is for an algorithms class currently dealing with ...
1
vote
1answer
17 views

Graph Theory: Conditional Expected Value of Product of two Random Variables

Consider a graph with $n$ vertices, where each edge between any two vertices is independently drawn with probability $p$. Let $D_i$ be the degree of vertex $i$. What is $E[D_i \cdot D_j]$? Here is ...
3
votes
1answer
42 views

Class of graphs with symmetric random walk

Let $(V,E)$ be a graph and let $X_n$ be a random walk on the graph. At every step, the walker at $x$ jumps to one of the neighbors drawn uniformly at random among all the vertices $y$ such that there ...
1
vote
1answer
34 views

Let $G$ be a graph on $n$ vertices, where $n \geq 3$. Suppose that $\Delta(G) \geq n/2$. Can $G$ have more than one component?

Let $G$ be a graph on $n$ vertices, where $n \geq 3$. Suppose that $\Delta(G) \geq n/2$. Can $G$ have more than one component? i did this for $n=3$ $\Delta(G) \geq 1.5$ as $\Delta.1$ component. for ...
0
votes
0answers
37 views

The length of a shortest path from $u$ to $v$ in a connected graph $G$ equals the level of $v$ in any BFS tree of $G$ with $u$ as root

I am studying graph theory but I cannot solve this question. Can you help me? "The length of a shortest path from $u$ to $v$ in a connected graph $G$ equals the level of $v$ in any BFS tree of $G$ ...
-1
votes
0answers
21 views

Is it true that any 20 regular graph has a path of length at least 10? [duplicate]

hi i am confused with this question."Is it true that any 20 regular graph has a path of length at least 10?" Does this make sense?
-1
votes
1answer
39 views

Can a graph with no cut edges contain a cut vertex [on hold]

hi can you help with this question. "Can a graph with no cut edges contain a cut vertex?"
0
votes
0answers
14 views

Kruskal's algorithm - Find the tree with the least possible weight

I need to find the tree with the least possible weight with Kruskal's algorithm. Here is my attempt: B-E-F-A-D and then I get stuck. Is my attempt looking correct? How should I continue?
0
votes
1answer
39 views

Graph Theory-Breadth First Search

I've been asked the following: Show that the length of the shortest path from $u$ to $v$ in a connected graph $G$ equals the level of $v$ in any BFS tree of $G$ rooted at $u$. I can't find any proof ...
-1
votes
0answers
39 views

Watts-Strogatz graphs

I'm stuck with this particular question. Can someone explain/help me? Suppose we construct a graph in $WS(n,k,p)$, starting from the n vertices in a ring, where each vertex is connected to its first ...
0
votes
1answer
15 views

If $G$ is a connected graph with $n$ vertices and$ n - 1$ edges then $G$ is a tree, using Induction.

I am still new to proof methods and not sure if this is the correct use of induction. Base case: $n = 1$ has $0$ edges and is a tree. Assume every connected graph with $k$ vertices and $k-1$ edges ...
2
votes
1answer
24 views

Understanding the set of neighbors of a set

For a graph G(V, E), the Hall's theorem states If for every subset X of V we have that |N(X)| ≥ |X|, then G has a perfect matching where N(X) represents the set of neighbors of the set X in G. ...
2
votes
0answers
49 views

ER graphs, expected number of triangles incident to one vertex

I'm really sorry for this question. I'm new to a graph theory, and I hope you will help me to understand one statement. Consider $ER(n,p)$ graph with $n \geq 3$ and $p \in [0,1]$. The statement ...
-1
votes
1answer
60 views

Regular graph path length problem [on hold]

Is it true that any $20$ regular graph has a path of length at least $10$? Can anyone please help me? I think there is a shorter path, but I can't be sure.
0
votes
0answers
13 views

graph theory-Eulerian

Graph G all vertices are even degree,it is Eulerian.Let W be a longest trail then I prove that it is closed trail.Then,suppose W is not Euler tour.I am going to show it is wrong proof by contradiction ...
0
votes
0answers
11 views

Sample data for a social graph

I wanted to use my facebook friends to create a social graph with around 50-100 nodes just to analyse mutual friendships, however it seems in a recent version of their graph API they prevent ...
1
vote
0answers
26 views

When do a Regular graph has an odd eigenvalue?

Merely looking at adjacency matrix of a regular graph, without explicit calculation, can we decide that graph will have an odd eigenvalue or not? If regularity is odd, we are sure that it will be an ...
0
votes
0answers
22 views

tripartite graph with n vertices

What is the maximum number of edges in a tripartite graph with n vertices? a k-partite graph with n vertices? I know that bipartite graph has $\frac {n^2}{4}$ max edges
1
vote
0answers
9 views

Maximum number of transitive triples in 3-partite diconnected tournament

Show that if $T$ is strongly connected 3-partite tournament with partite sets $V_0,V_1,V_2$ then the maximum number of transitive triples is $|V_0||V_1||V_2|-1$, unless $|V_0|=|V_1|=|V_2|=2$, in ...
0
votes
0answers
16 views

Eulerian circuit for connected graph with even degree vertices

Let $G$ be a connected graph where every vertex has even degree. Show that $G$ has an Eulerian circuit. Certainly the converse is true and is not hard to show.
1
vote
1answer
16 views

Proving that in a complete graph $\lambda(K_{n}) = \delta(K_{n})$

Since $K_{n}$ is n-1 regular. Then $\lambda(G)$ must be n-1. Since $\lambda(K_{n}) \leq \delta(K_{n})$ then by definition they must be equivalent. Can I use the definition or should I say since ...
1
vote
1answer
17 views

Proving that in a complete graph $\kappa(K_{n}) = \delta(K_{n})$

Since $K_{n}$ is n-1 regular. Then $\delta(G)$ must be n-1. Since $\kappa(K_{n}) \leq \delta(K_{n})$ then by definition they must be equivalent. Am I approaching this proof the right way?
0
votes
0answers
22 views

Graphs having only four cycles [on hold]

If a connected bipartite graph has only four cycles, what can you say about the degrees of its vertices? Like 1. all the four cycles are pairwise disjoint. 2.two cycles may have one or two edges ...
1
vote
1answer
27 views

Graph Theory + Dynamical Systems

Suppose you had a dynamical system $\dot{\vec{x}} = \vec{f}(\vec{x})$. In theory, one could represent this as a directed graph where the vertices are fixed points of the dynamical system and the edges ...
0
votes
0answers
19 views

Meaning of complement of vertex and edge sets

I am reading about maximum bipartite matching and everywhere I look there is thing: $$ U':=U\setminus M $$ Sometimes it's written like this: $$ U':=U\setminus\cup M $$ where $U$ is a set of vertices ...
2
votes
1answer
26 views

Apply Hall's theorem to a problem

I have only seen Hall's theorem applied on the marriage problem. For the problem below I have to use this theorem I guess. For me it's still difficult to apply this to a problem. Problem: Consider ...
1
vote
1answer
17 views

Counting Subgraphs of simple graphs

Assuming $r\le n$ What is the number of subgraphs $K_r$ in $K_n$? I am not sure if this one is just $n \choose r$ or I have to divide that by 2? What is the number of subgraphs $P_r$ in $K_n$? Is it ...
0
votes
0answers
10 views

Residual network in undirected graph

I want to find minimum s-t cut in undirected graph. I use Ford–Fulkerson algorithm for my graph. This algorithm returns |min_cut|, but I want to get edges, which ...
0
votes
0answers
17 views

Solutions Manual for Fundamentals of Domination in Graphs

Is there a solutions manual for: T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds.), Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998. If so, how do I obtain it?
0
votes
0answers
20 views

Subgraphs comparison

I am comparing a set of pairs of subgraphs of the same complete undirected graph and need to identify pairs where members are similar to each other. After some consideration, I've ended up with ...
3
votes
2answers
27 views

Restricting a relation to an injective function

Given a relation between two finite sets, how can I determine whether it restricts to an injective function? The criterion or algorithm doesn't need to be constructive: It is enough to know that such ...
-1
votes
0answers
37 views

What is the number of (un-)directioned relation, Among the sets and their elements …F^^?? [on hold]

Q1. There are sets named "Α", "Β", "Γ", .... , "Ω" .Each set has elements. Their total number is 'n_α ', 'n_β ', 'n_γ ', .... , 'n_ω ' . For the simplicity, we prescribe, here,  that all the ...
0
votes
1answer
31 views

How to represent n-cube graph in form of a set?

Can we represent an n-cube graph in the form of a set of edges? If so, then how can we represent a Q4 graph?
0
votes
2answers
41 views

Why are these two graphs isomorphic?

I have the following graphs and I am trying to identify if they are isomorphic or not. The solutions that I have indicate they are isomorphic, with the following bijection: However, it appears ...
1
vote
0answers
29 views

How can you find the total number of non-isomorphic unlabeled graphs with n vertices?

I have seen some questions about labeled graphs, but no answers for an unlabeled graph. I calculated for the first four graphs and it seems to be $2n-1$ total graphs for $n$ vertices. I'm not sure if ...
0
votes
2answers
29 views

Edge that does not appear in ANY spanning tree?

I have a problem that just puzzles me... I am told I have a graph $G$ and asked what I can say about an edge that appears in no spanning tree of $G$. My question is...is there such an edge to start ...
1
vote
2answers
24 views

Euler Formula for planar graphs

Sorry to post questions so many times...but I'm confused with what use Euler's formula for planar graphs has. Because, say, $K_4$ the complete graph with 4 vertices is planar after some rearranging ...
1
vote
1answer
26 views

Closed form of S(n):

The following problem is about a game played with wooden blocks stacked vertically. The way the game is played is as so: There is a stack of n blocks available on a table in front of you; With ...