Questions tagged [graph-connectivity]

For questions related to the vertex-connectivity or edge-connectivity of graphs or networks: the minimum number of vertices (respectively edges) that need to be deleted to disconnect the graph.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
41 views

The contraction two graphs maintain the connectivity?

Let $G$ be a graph. For $X \subseteq E(G)$, define $G[X] = (V(G), X)$. I know that $u$ and $v$ are connected in $H[A]$ if and only if $u$ and $v$ are connected in $H[B]$ and let $Z \subseteq E(H)$ ...
user avatar
  • 93
0 votes
0 answers
29 views

Showing edge-connectivity greater than vertex-connectivity

The following is quoted from Diestel's Graph Theory: Proposition 1.4.2. If $G$ is non-trivial then $\kappa(G) \leqslant \lambda(G) \leqslant \delta(G)$. Proof. The second inequality follows from the ...
user avatar
  • 1,432
4 votes
2 answers
97 views

What is the probability that two nodes are connected in a random graph?

I have just started with the theory of random graphs. I have come across the following expression of the probability that two nodes $i$ and $j$ are connected where $k_i$ and $k_j$ are the respective ...
user avatar
  • 155
0 votes
1 answer
29 views

Subset of the plane with no infinite set of disjoint $A-B$ arcs.

I want to find a subset $D$ of the plane such that has two infinite setss $A,B\subseteq D$ for which every finite set $X\subseteq D$ there is an $A-B$ arc in $D-X$ but $D$ contains no infinite set of ...
user avatar
  • 283
2 votes
1 answer
38 views

A Result on Cut Vertices

This is one of the steps used to prove Menger's theorem in question 4 part (iii) of https://uwaterloo.ca/combinatorics-and-optimization/sites/ca.combinatorics-and-optimization/files/uploads/files/...
user avatar
  • 1,191
0 votes
2 answers
31 views

How I can show that the swap of edges not change the original connectivity

Let $G$ be a graph. We say that $u$ and $v$ are connected in $G$, if exists a path of $u$ to $v$ in $G$. I wish show the following: Let $F$ be a forest and $T_1$ a tree with $T_1 \subseteq F$ (...
user avatar
  • 93
3 votes
1 answer
42 views

Finite orientation/colouring of an infinite clique graph

Let $X$ be an infinite set and consider the undirected clique graph $Q(X)$. That is, $Q(X)$ has an edge between $x$ and $x'$ in $X$ for every distinct $x$ and $x'$. My question is this: In what ...
user avatar
  • 117
0 votes
0 answers
30 views

The only cut vertex in a graph

Let a graph $G$ be arbitrarily traversable from a vertex $v$, i.e., any trail in $G$ initiatng from $v$ ultimately results in an Eulerian $v-v$ circuit. Let $v$ be a cut-vertex in $G$. Is it true that ...
user avatar
  • 5,585
0 votes
0 answers
33 views

Brooks' Theorem Time complexity

I am looking to derive an algorithm that finds, for every connected graph $G$ that is neither complete nor an odd cycle, a $\Delta(G)$-colouring in time $O(m+n)$. When we proved Brooks' theorem we ...
user avatar
  • 77
1 vote
0 answers
70 views

How can I show that for each $e = uv \in F_0$ we have $H[F^* \cup e]$ contains a cycle

First, I present some definitions. Let $G$ a graph. For each $Z \subseteq E(G)$, we denote the graph $G[Z]$ by the $(V(G), Z)$. Let ${\cal P}$ a partition of $V(G)$. Define the graph $G_{\cal P}$ ...
user avatar
  • 93
2 votes
1 answer
49 views

Why is this simple proof of the fact $\kappa(G)\le \lambda(G)$ is wrong?

A standard result in graph theory(more specifically graph connectivity) is that $\kappa(G)\le \lambda(G)$, where $\kappa(G)$ is the size of vertex cut set of $G$ and $\lambda(G)$ is the size of the ...
user avatar
1 vote
1 answer
23 views

Deduce the undirected edge version of Menger's theorem from the directed version

Menger's theorem says, in directed graph $G$, $k$ is the maximum number of arc-disjoint $st$-dipaths if and only if the size of the minimum $st$-cut is $k$. Use this version of Menger's theorem to ...
user avatar
  • 13
4 votes
1 answer
51 views

Proving that disconnecting edges of a 3-edge-colorable graph are of the same color

I'm struggling to prove the following: Edges of a connected cubic graph G can be colored with 3 colors in such a way that no adjacent edges are of the same color. 2 edges were removed from the graph ...
user avatar
  • 93
5 votes
1 answer
84 views

Finding a spanning tree with at least 100 leaves

I have the following graph theory problem: In a country there are pairs of towns connected by roads in such a way that you can get from any town to any by those roads. The president of the country ...
user avatar
  • 93
1 vote
1 answer
59 views

Finding optimal minimum rooted k-edge disjoint connected paths to build a feasible solution for the undirected version

Suppose we have an undirected weighted graph G with a root node, and the goal is to find minimum cost k-edge disjoint paths from the root node to each vertex. Now, suppose we create a directed version ...
user avatar
  • 137
0 votes
1 answer
31 views

Relationship between the minimum cost rooted k-edge connected subgraph and the unrootd version in undirected graphs

In the undirected rooted k-edge connected subgraph problem, the goal is to find a minimum cost subgraph in which there are k edge-disjoint paths between the root and each vertex in the graph. The ...
user avatar
  • 137
0 votes
1 answer
40 views

Can vertex connectivity of a plane graph be characterized by a special closed Jordan curve?

Let $P$ be a plane, and a simple closed curve $l$ on $P$ is separating if $P-l$ is not connected. My question is as follows. Question Let $G$ be a planar graph with connectivity $k$, and $\phi(G)$ be ...
user avatar
  • 737
0 votes
0 answers
7 views

What are real life examples of the arc augmentation problem in tournaments, semicomplete digraphs or locally semicomplete digraphs?

Suppose we have a digraph $G=(V,A)$ that is not yet $k$-strong. Assuming parallel arcs are not allowed, as long as $|V|\geq k+1$ we can always add a number of arcs to $A$ to make $G$ $k$-strong. ...
user avatar
  • 107
0 votes
0 answers
28 views

Does block graph with one vertex exists?

A definition on Wolfram and Wikipedia suggest to me that a block graph contains connected components. A graph with one vertex is connected. Since one-vertex graph has 1-component and not components, a ...
user avatar
  • 637
1 vote
1 answer
39 views

4-cycle addition converts a quadrangulation graph with 2-connectivity into a 3-connected quadrangulation .

Let $H$ be a quadrangulation on the sphere and let $f$ be a face of $H$ bounded by a $4$-cycle $∂f = v_1v_2v_3v_4$. A $4$-cycle addition to $f$ is to put a 4-cycle $u_1u_2u_3u_4$ inside $f$ and join $...
user avatar
  • 737
0 votes
0 answers
69 views

Halving number of d-dimensional cube

I am interested in showing that the halving number of the d-dimensional cube is $2^{d-1}$ for $d = 1, 2$ but not for $d \ge 3$. I tried to find the meaning of $\textit{halving number}$ but I couldn't ...
user avatar
  • 637
0 votes
0 answers
36 views

Longest cycles in 2-connected graph having exactly two nodes in common

$\textbf{Question}-$ I was reading this and that which prompted me to want identify an example of a 2-connected graph where $\textit{some pair of longest cycles}$ have exactly two vertices in common. $...
user avatar
  • 637
0 votes
1 answer
86 views

Examples based on a 2-connected graph.

According to Scott Smith 1984 Conjecture: In a $k$-connected graph, where $k \ge 2$, any two longest cycles have at least $k$ vertices in common. A 2-connected graph: every pair of longest cycles have ...
user avatar
  • 637
0 votes
0 answers
42 views

Randomly matchable and bipartite class

I am curios to know at least one example of the following graphs: i) an infinite class of bipartite graphs that is randomly matchable; ii) an infinite class of non-bipartite graphs that is randomly ...
user avatar
  • 637
3 votes
1 answer
35 views

Definition of "separate" in Diestels‘s Graph Theory

In Dietels Graph theory, he defined "separate" in chapter 1.4 as If $A, B \subseteq V$ and $X \subseteq V \cup E$ are such that every $A-B$ path in $G$ contains a vertex or an edge from $X$,...
user avatar
1 vote
1 answer
38 views

Number of pairwise non isomorphic 2-connected graph with no $K_4^-$ minor

I had this question in my graph theory exam today, and I'm pretty sure I answered it wrong. We define $K_4^-$ as $K_4$ with one less edge. Find the number of pairwise non isomorphic graphs $G$, such ...
user avatar
2 votes
0 answers
63 views

A 2-connected graph example

$\textbf{Question:}$ In a $k$-connected graph $(k\ge2)$, any $k$ vertices lie on a common cycle. $\textbf{Proof:}$ Let $S$ be a given set of $k$ vertices and consider a cycle $C$ with the maximum ...
user avatar
  • 637
0 votes
0 answers
84 views

Lower Bounds on edge connectivity for expander graphs

So I've been messing around with expander graphs, and since their advantage is to maintain a high 'connectivity' with a fixed degree, I wondered about their edge connectivity. Formally, fix $k \ge 2$ ...
user avatar
1 vote
1 answer
45 views

How can a "bridge path" in an undirected graph be defined correctly/mathematically precisely?

How would you define an undirected graph containing a path solely of bridges like: Connected Subgraph<->*<->*<->*<->* (* node; <-> undirected edge) Alternatively: ...
user avatar
  • 243
0 votes
0 answers
29 views

Checking reachability and specifying direction and color of edges of a bigraph

I need help in finding a solution to this problem and answering my questions: first: is there any particular name for this problem? second: how can we solve it? third: it is not always possible to ...
user avatar
2 votes
0 answers
34 views

Is a random $(r+1,r)$-biregular bipartite graph $r$-edge connected w.h.p?

A uniformly random $r$-regular bipartite graph is known to be $r$-edge connected. That is, with high probability as $n$ grows large, the minimum size of a cut in a random $r$-regular bipartite graph ...
user avatar
1 vote
1 answer
165 views

Question about maximal connected subgraph [closed]

A maximal connected subgraph of G is a connected subgraph of G that is maximal with respect to the property of connectedness. This is called a component of G. Visually, components of G are the pieces ...
user avatar
0 votes
1 answer
61 views

Proof that either $G$ or its complement $\bar{G}$ is connected by induction

I wrote the following inductive proof, but I don't know if it is valid and if there are any points that I'm missing. I got a bit lost trying to prove the inductive step. We prove this statement by ...
user avatar
0 votes
3 answers
48 views

Questions concerning connectivity of graphs

So, we have been working with graphs for a while now and the profesor has handed out some questions for us to think. There are 3 of them that caught my attention: May the graph with 4,3,3,3,3,1,1 ...
user avatar
1 vote
1 answer
31 views

Ensure weak connectivity in all k-out k-regular graphs depending on the number of vertices

When generating a random k-out k-regular directed graph, each node chooses randomly a distinct set of k nodes and creates k out-edges to them. I've only found results to my first question where $P = 1$...
user avatar
  • 123
1 vote
1 answer
45 views

Does it matter where we start on an Euler graph?

For a graph to be an euler graph, all the vertices have to be of even degree...I was wondering "does which vertex to start matter?"...I played around and now I kind of think it doesn't ...
user avatar
  • 57
1 vote
1 answer
44 views

Partition of graph with $\lambda(G)$

Let $\lambda(G)=\min\{|X|:X \subset E(G) \wedge G-Y \text{ is not connected} \}$ (minimum number of edged to delete to disconnect conntected graph). Let $\lambda(G) = k > 0$. Show that there is ...
user avatar
  • 253
1 vote
0 answers
38 views

Proof verification on $2$-connected Graph

A Graph is $2$-connected iff each two vertices lie on the same cycle. Proof: left to right: Graph is $2$-connected if each $2$ vertices are connected with at least two disjoint paths(follows from ...
user avatar
  • 777
1 vote
0 answers
87 views

Characterization of graphs with vertex-connectivity equal to edge-connectivity

Are there any attempts to characterize (simple, finite) graphs with vertex-connectivity $\kappa$ equal edge-connectivity $\kappa'$? In general, $\kappa(G)\leq \kappa'(G)\leq \delta(G)$ where $\delta(G)...
user avatar
4 votes
1 answer
134 views

$k$-connected graph $G$ with $n$ vertices has a cycle of length at least $3k$ if $n\ge 3$ and $C_4\not\subseteq G$

Problem 7.2.32 in Combinatorial Mathematics by Douglas B. West. The complete question is: Fix $k\ge 2$, and let $G$ be a $k$-connected graph with $n$ vertices. For $n\ge 3k$, prove that $G$ has a ...
user avatar
  • 479
1 vote
1 answer
173 views

Prove that minimally 2-connected graphs have a vertex of order 2?

I need help proving that every minimally 2-connected graph has a vertex of order 2 (the order of a vertex being equal to the number of edges that "enters" it). By definition, a graph is 2-...
user avatar
  • 55
3 votes
1 answer
326 views

Proof that every 2-connected graph has at least one contractible edge.

I am trying to prove the following statement: An edge $e$ in a 2-connected graph $e$ is said to be contractible if $G/e$ is also 2-connected. Prove that every 2-connected graph of order at least 3 ...
user avatar
  • 33
0 votes
1 answer
38 views

Vertex connectivity of a graph and matchings

Let $G$ be a graph with pairwise disjoint vertex classes $A$, $C$ and $B$, such that there is no edge from a vertex in $A$ to a vertex in $B$ and the cardinality of $C$ equals the vertex connectivity ...
user avatar
  • 2,587
3 votes
1 answer
101 views

Show that a minimal solution has degree at most 2

Given a graph $G=(V,E)$, and a set $T\subseteq V$ of terminals, we say that $S \subseteq V\setminus T$ is feasible if $G[T\cup S]$ is connected. In other words, a feasible solution is a set of non-...
user avatar
0 votes
0 answers
37 views

not quite biconnected component in DAGs

In undirected graphs, a "biconnected component" is a maximal subgraph containing no cut-vertices, that is, vertices whose deletion increases the number of connected components. For directed ...
user avatar
  • 168
1 vote
1 answer
127 views

A connected component of a graph G is a connected subgraph of G that is not a proper subgraph of another connected subgraph of G?

I'm reading Graph Theory from Kenneth H. Rosen. A connected component of a graph G is a connected subgraph of G that is not a proper subgraph of another connected subgraph of G. That is, a connected ...
user avatar
  • 101
1 vote
1 answer
157 views

Two independent spanning trees of $2$-connected graph

I want to prove the following statement: Let $u$ be a vertex in a $2$-connected graph $G$. Then $G$ has two spanning trees such that for every vertex $v$, the $u,v$-paths in the trees are independent....
user avatar
  • 621
1 vote
1 answer
88 views

Same edge-connectivity and the minimum degree in bipartite graph

Let $G$ be a $n$-order bipartite graph. $\kappa'(G)$ is an edge-connectivity of $G$, and $\delta(G)$ is the minimum degree of $G$. I want to prove the following theorem: If $\delta(G) \geq \frac{n}{4}...
user avatar
  • 621
0 votes
1 answer
28 views

Definition of $\mathfrak a$-connected graphs?

A typical definition of a graph $G$ being $k$-connected ($k\in\mathbb N_0$) is this: $k<|G|$ (the order of $G$) and for $X$ being a subset of $V(G)$ such that $|X|<k$ holds $G\setminus X$ is ...
user avatar
  • 2,785
0 votes
0 answers
46 views

Prove that $6$ regular graph is connected

My question is how to check whether $6$ regular graph with $16$ vertices is connected or not? I found that number of edges is $48$ and then because $48 < {15 \choose 2}$ we can't say anything about ...
user avatar
  • 503

1
2 3 4 5
7