Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCharacterising $k$-connected sets in infinite graphs
87
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A $k$-connected set in an infinite graph, where $k > 0$ is an integer, is a set of vertices such that any two of its subsets of the same size $ell leq k$ can be connected by $ell$ disjoint paths in the whole graph. We characterise the existence of $k$-connected sets of arbitrary but fixed infinite cardinality via the existence of certain minors and topological minors. We also prove a duality theorem for the existence of such $k$-connected sets: if a graph contains no such $k$-connected set, then it has a tree-decomposition which, whenever it exists, precludes the existence of such a $k$-connected set.
rate research
Read More
For a graph G=(V,E), the k-dominating graph of G, denoted by $D_{k}(G)$, has vertices corresponding to the dominating sets of G having cardinality at most k, where two vertices of $D_{k}(G)$ are adjacent if and only if the dominating set corresponding to one of the vertices can be obtained from the dominating set corresponding to the second vertex by the addition or deletion of a single vertex. We denote by $d_{0}(G)$ the smallest integer for which $D_{k}(G)$ is connected for all k greater than or equal to $d_{0}(G)$. It is known that $d_{0}(G)$ lies between $Gamma(G)+1$ and $|V|$ (inclusive), where ${Gamma}(G)$ is the upper domination number of G, but constructing a graph G such that $d_{0}(G)>{Gamma}(G)+1$ appears to be difficult. We present two related constructions. The first construction shows that for each integer k greater than or equal to 3 and each integer r from 1 to k-1, there exists a graph $G_{k,r}$ such that ${Gamma}(G_{k,r})=k, {gamma}(G_{k,r})=r+1$ and $d_{0}(G_{k,r})=k+r={Gamma}(G)+{gamma}(G)-1$. The second construction shows that for each integer k greater than or equal to 3 and each integer r from 1 to k-1, there exists a graph $Q_{k,r}$ such that ${Gamma}(Q_{k,r})=k, {gamma}(Q_{k,r})=r$ and $d_{0}(Q_{k,r})=k+r={Gamma}(G)+{gamma}(G)$.
Halin showed that every edge minimal, k-vertex connected graph has a vertex of degree k. In this note, we prove the analogue to Halins theorem for edge-minimal, k-edge-connected graphs. We show there are two vertices of degree k in every edge-minimal, k-edge-connected graph.
Given a set $F$ of words, one associates to each word $w$ in $F$ an undirected graph, called its extension graph, and which describes the possible extensions of $w$ on the left and on the right. We investigate the family of sets of words defined by the property of the extension graph of each word in the set to be acyclic or connected or a tree. We prove that in a uniformly recurrent tree set, the sets of first return words are bases of the free group on the alphabet. Concerning acyclic sets, we prove as a main result that a set $F$ is acyclic if and only if any bifix code included in $F$ is a basis of the subgroup that it generates.
Tree sets are abstract structures that can be used to model various tree-shaped objects in combinatorics. Finite tree sets can be represented by finite graph-theoretical trees. We extend this representation theory to infinite tree sets. First we characterise those tree sets that can be represented by tree sets arising from infinite trees; these are precisely those tree sets without a chain of order type ${omega+1}$. Then we introduce and study a topological generalisation of infinite trees which can have limit edges, and show that every infinite tree set can be represented by the tree set admitted by a suitable such tree-like space.
We adapt the classical 3-decomposition of any 2-connected graph to the case of simple graphs (no loops or multiple edges). By analogy with the block-cutpoint tree of a connected graph, we deduce from this decomposition a bicolored tree tc(g) associated with any 2-connected graph g, whose white vertices are the 3-components of g (3-connected components or polygons) and whose black vertices are bonds linking together these 3-components, arising from separating pairs of vertices of g. Two fundamental relationships on graphs and networks follow from this construction. The first one is a dissymmetry theorem which leads to the expression of the class B=B(F) of 2-connected graphs, all of whose 3-connected components belong to a given class F of 3-connected graphs, in terms of various rootings of B. The second one is a functional equation which characterizes the corresponding class R=R(F) of two-pole networks all of whose 3-connected components are in F. All the rootings of B are then expressed in terms of F and R. There follow corresponding identities for all the associated series, in particular the edge index series. Numerous enumerative consequences are discussed.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
