Paths containing two adjacent edges in (2k+1)-edge-connected graphs

We consider finite undirected graphs, possibly with multiple edges but without loops. Let \(G\) be a graph and let \(V(G)\) and \(E(G)\) be the set of vertices and edges of \(G\), respectively. We allow a repetition of vertices (but not edges) in a path and cycle. For \(x,y\in V(G)\), \(\lambda(x,y;G)\) denotes the maximal number of edge-disjoint paths between \(x\) and \(y\), a path \(P= P[x,y]\) denotes a path between \(x\) and \(y\), and \(\lambda(G)=\min_{x,y\in V(G)} \lambda(x,y;G)\). For \(X,Y\subset V(G)\), with \(X\cap Y=\varnothing\), \(\partial(X,Y;G)\) denotes the set of edges with one end in \(X\) and the other in \(Y\), and set \(\partial(X;G)= \partial(X,V(G)-X;G)\), \(e(X,Y;G)=|\partial(X,Y;G)|\) and \(e(X;G)=|\partial(X;G)|\). In the notations, we often omit \(G\). We set \(\Gamma(G,k)=\{Z\subset V(G)|\) for each \(a,b\in Z\), \(\lambda(a,b:G)\geq k\}\). For natural numbers \(k\geq n\), we call a path (or cycle) \(P\) in \(G\) \(n\)-reducible if \(\lambda(G)\geq k\) and \(\lambda(G- E(P))\geq k-n\). If \(P\) contains a vertex of degree \(k\) as an inner vertex, then \(P\) is not 1-reducible. The problem we consider is what kinds of 2- reducible paths and cycles there exist. Lemma 2.1 gives one answer to this problem. For even \(k\), we can find much more 2-reducible paths and cycles.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Paths containing two adjacent edges in \((2k+1)\)-edge-connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686504)