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

Matrix irreducibility. Strongly connected graph

I have this theorem from Combinatorial Matrix Theory written by Richard A. Brualdi and others. Let $A$ be a matrix of order $n$. Then $A$ is irreducible if and only if its digraph $D$ is strongly ...
1
vote
0answers
17 views

Serialize Node Graph to integer

Is it possible to serialize a node graph into an integer, in a way that it is recoverable? For example: ...
0
votes
0answers
11 views

relation between regular and distance-regular graphs [on hold]

What is the relationship between regular and distance-regular graphs?
1
vote
1answer
35 views

covering subsets

Let $A=\left\{ {1, 2, \ldots, n}\right\}$. Let $B$ be the set of all size $m$ subsets of $A$. $B=\left\{{B_1,B_2, \ldots , B_{\binom{n}{m}} } \right\}$, $ |B_i|=m$ then we want to find $k$ subsets ...
1
vote
0answers
17 views

What is the Möbius analoge for Ihara's $\zeta$ function?

The Dirichlet series that generates the Möbius function is the (multiplicative) inverse of the Riemann zeta function; if s is a complex number with real part larger than 1 we have $$ ...
1
vote
1answer
18 views

Prove that graph $G$ is bipartite iff every $H\subseteq G$ has linearly independent group of vertices

Prove that graph $G$ is bipartite iff every $H\subseteq G$ has linearly independent group of vertices of size $\leq |V'|/2$. (where $G=(V,E)$ ,$ H=(V',E')$) I managed to prove the first part myself ...
0
votes
0answers
21 views

Induction graph theory - dealing with reducing the problem

I have a general question regarding induction in graph theory. Often I am required to use induction in order to prove a theorm. I have seen a lot of cases in which the reduction of the problem was ...
1
vote
2answers
30 views

graph degrees question (combinatorics)

let it be $(d_1,d_2,...,d_n)$ which represents a series of positive integer numbers, so that $n\gt d1 \gt d2 \gt ... \gt d_n \ge 0$. let it be $K\ge d_1$. given that $(K,d_2,...,d_n,1,1...,1)$ ...
1
vote
0answers
11 views

cardinality of the maximum independent set for a given degree distribution

Consider undirected graph $G(V,E)$. Assume that $f_n(k)$ be the probability mass function of degree of a vertex in $G$. Further, assume that $f_n(k)$ is an strictly decreasing function of $k$ with ...
0
votes
2answers
49 views

How do you find the value of n in this example

$$n^{n-2} = 16$$ I know $n = 4$ through trial and error but how do you find $n$ in a conventional manner? I'm basically trying to solve how many nodes are in a tree that has $16$ spanning trees ...
3
votes
1answer
24 views

Book recommendation for network theory

I'm looking for a mathematically rigorous book on Network theory covering topics like entropy, degree distribution, centrality, and regular, random, small-world and scale-free networks. I'm familiar ...
2
votes
1answer
56 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 ...
1
vote
1answer
47 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
58 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
35 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
37 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
16 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
34 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
20 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
27 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
28 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
18 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
1answer
20 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 ...
0
votes
0answers
41 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
52 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
12 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
27 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
23 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
18 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 [closed]

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
28 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 ...