Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA synthesis for exactly 3-edge-connected graphs
212
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A multigraph is exactly k-edge-connected if there are exactly k edge-disjoint paths between any pair of vertices. We characterize the class of exactly 3-edge-connected graphs, giving a synthesis involving two operations by which every exactly 3-edge-connected multigraph can be generated. Slightly modified syntheses give the planar exactly 3-edge-connected graphs and the exactly 3-edge-connected graphs with the fewest possible edges.
rate research
Read More
A finite graph $G$ is said to be {em $(G,3)$-$($connected$)$ homogeneous} if every isomorphism between any two isomorphic (connected) subgraphs of order at most $3$ extends to an automorphism $gin G$ of the graph, where $G$ is a group of automorphisms of the graph. In 1985, Cameron and Macpherson determined all finite $(G, 3)$-homogeneous graphs. In this paper, we develop a method for characterising $(G,3)$-connected homogeneous graphs. It is shown that for a finite $(G,3)$-connected homogeneous graph $G=(V, E)$, either $G_v^{G(v)}$ is $2$--transitive or $G_v^{G(v)}$ is of rank $3$ and $G$ has girth $3$, and that the class of finite $(G,3)$-connected homogeneous graphs is closed under taking normal quotients. This leads us to study graphs where $G$ is quasiprimitive on $V$. We determine the possible quasiprimitive types for $G$ in this case and give new constructions of examples for some possible types.
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.
This paper begins the classification of all edge-primitive 3-arc-transitive graphs by classifying all such graphs where the automorphism group is an almost simple group with socle an alternating or sporadic group, and all such graphs where the automorphism group is an almost simple classical group with a vertex-stabiliser acting faithfully on the set of neighbours.
In 2006, Barat and Thomassen posed the following conjecture: for each tree $T$, there exists a natural number $k_T$ such that, if $G$ is a $k_T$-edge-connected graph and $|E(G)|$ is divisible by $|E(T)|$, then $G$ admits a decomposition into copies of $T$. This conjecture was verified for stars, some bistars, paths of length $3$, $5$, and $2^r$ for every positive integer $r$. We prove that this conjecture holds for paths of any fixed length.
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)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
