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
votes
1answer
22 views

number of walks of length equal to the size of the edge list

Let the graph $G$ and the non-empty list $(e_i ~| ~i \in 1, ... n)$ in $E(G)$ be given. There exists at most one walk of length $n$ in $G$ with $(e_i ~| ~i \in 1, ..., n)$ as its edge list, unless ...
0
votes
0answers
4 views

Cardinality of 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 ...
1
vote
0answers
13 views

Collapsing and Expanding a forest graph (how to proof that $exp\circ col \neq id $ ? )

I'm trying to understand this map: Let $f: G \to G$ be a graph map and let $G_0$ be a forest in graph $G$. Let $ G/G_0$ be the graph obtained by collapsing each connected component of $G_0$ to a ...
0
votes
0answers
9 views

how to find out how many minimum spanning trees does a graph have [on hold]

so i was wondering what method can someone use to find the amount of MSTs in a graph Thanks in advance
0
votes
0answers
9 views

Where is Degree-Diameter Problem table?

Degree-Diameter Problem is a well known problem in graph theory. http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem I found the table for small diameter and small degree. ...
0
votes
0answers
9 views

Non negative irreducible matrix implies there is a strictly positive power.

How can I proof that a non negative irreducible matrix necessarily has a strictly positive power? By irreducible matrix i understand this http://mathworld.wolfram.com/ReducibleMatrix.html It looks ...
1
vote
1answer
23 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
18 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
40 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 ...
2
votes
0answers
21 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
22 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 ...
1
vote
0answers
25 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
1answer
31 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)$ ...
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
27 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
59 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
36 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
39 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
36 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
21 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
29 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
39 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
19 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 [closed]

hi can you help with this question. "Can a graph with no cut edges contain a cut vertex?"
0
votes
1answer
21 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
42 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
53 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 [closed]

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