Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Recent questions tagged graph-connectivity

2 votes
3 answers
Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: diam$(G)=\displaystyle \max_{u,v\in V} \{$the length of shortest path between $u$ and $v\}$ Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ on the same set of vertices with adjacency ... diam$(G)/2\rceil<$diam$(G_2)<$ diam$(G)$ diam$(G_2)$ = diam$(G)$ diam$(G)<$ diam$(G_2)\leq 2 $ diam$(G)$
asked Feb 18 in Graph Theory Arjun 416 views
0 votes
1 answer
Consider the assertion: Any connected undirected graph $G$ with at least two vertices contains a vertex $v$ such that deleting $v$ from $G$ results in a connected graph. Either give a proof of the assertion, or give a counterexample (thereby disproving the assertion).
asked Sep 13, 2019 in Graph Theory gatecse 214 views
1 vote
1 answer
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented and each ... is: Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component
asked Sep 13, 2019 in Graph Theory gatecse 211 views
1 vote
1 answer
Let $G$ be a simple graph on $n$ vertices. Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.
asked Sep 13, 2019 in Graph Theory gatecse 164 views
1 vote
0 answers
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $0-1$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\leq n,$ the entry $A[i,j]=1$ ... which any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in $G.$ Analyze the time taken by your procedure.
asked Sep 13, 2019 in Graph Theory gatecse 116 views
1 vote
1 answer
I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them is But I think that a multi-stage graph is also a DAG. Are multi-stage graphs a special kind of DAG?
asked Apr 28, 2019 in Graph Theory gmrishikumar 276 views
0 votes
0 answers
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.
asked Apr 8, 2019 in Graph Theory akash.dinkar12 189 views