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

0
votes
0answers
18 views

Adjacency matrix multiplication

Let $G$ be a directed graph with 10 vertices. Let $A$ be the adjacency matrix for $G^3$ and $B$ the adjacency matrix for $G^4$. Describe in words what the product $AB$ represents. I know that the ...
1
vote
1answer
21 views

A question on $k$-connected graphs [duplicate]

I'm looking for a proof of this theorem by Dirac: If a graph is $k$-connected for $k \ge 2$, then for every set of $k$ vertices in the graph there is a cycle that passes through all the vertices in ...
1
vote
1answer
22 views

What is the difference between Maximal and Maximum Cliques

Hardly I can not find the clear differences between Maximal and Maximum Cliques, As I think Maximal means a graph can not be extended to connect more edges , means each node is connected with all ...
0
votes
2answers
15 views

what is the counter example to minimality of coloring a graph in BFS manner?

i was thinking of below algorithm i use a queue Q to performs BFS and i use an arbitrary start vertex s. each vertex v has attribute v.color which specifies it's color. ...
3
votes
0answers
13 views

Show that every cubic K4-free graph G has a bipartite subgraph with at least m-n/3 edges

Suppose $G$ is a cubic $K_4$-free Graph with $m$ edges and $n$ vertices, prove that there exists a bipartite subgraph of $G$ with at least $m-\frac{n}{3}$ edges. I can only prove we can find a ...
1
vote
1answer
19 views

How to find that two adjacency matrices are equal

What is the easiest way to tell if these two graphs are isomorphic and how do I know which nodes in both graphs are the same. I've made the adjacency matrices but they are pretty big. I think I need ...
0
votes
0answers
30 views

Why a graph $G=(V,E)$ has either one vertex $v\in V$ such that $\deg v\geq\sqrt n$ or all vertex has degree less that $\sqrt n$

We suppose $|V(G)|=n$. Why a graph $G=(V,E)$ has either one vertex $v\in V$ such that $\deg v\geq\sqrt n$ or all vertex has degree less that $\sqrt n$ ?
1
vote
1answer
10 views

Prove that if $\delta(V)\geq 2$, the graph $G=(V,E)$ has a cycle of length $\delta(V)+1$.

Let $\delta(G)=\min_{v\in V}d(v)$ where $d(v)$ is the degree of $v$. Prove that if $\delta(G)\geq 2$, the graph $G=(V,E)$ has a cycle of length $\delta(V)+1$. It look to have a problem... take ...
1
vote
0answers
15 views

How do we derive efficiency from robustness in the virtual ant solution to the traveling salesman problem?

Using virtual ants/swarm intelligence to solve the Traveling Salesman Problem is an example of using a robust system to solve an efficiency problem. We normally think of robustness and efficiency as ...
1
vote
1answer
10 views

Is the Turán graph $T_{k,n}$ vertex-transitive when $n$ is a multiple of $k$?

Take $k,n$ to be two positive integers, such that $n$ is a multiple of $k$, say $n= k m$ for some integer $m$. Consider the Turán graph $T_{k,n}$, i.e. the complete $k$-partite graph with $n$ vertices ...
1
vote
1answer
13 views

Finding number of Vertices and Edges of a Graph via Euler's Formula

Let $G$ be a simple $4$-regular connected graph, and suppose that $G$ is planar and has $10$ faces. (A graph is $4$-regular if all of its vertices have degree $4$.) Determine the number of edges of ...
0
votes
1answer
26 views

number of walks of length equal to the size of the edge list [on hold]

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
9 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
17 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
12 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
10 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
24 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
41 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
24 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
23 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
26 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
0answers
30 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
62 views

How to count the number of walks from $u$ to $v$ in a graph? [on hold]

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 [closed]

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
37 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
38 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
1answer
56 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 ...