There are numerous results bounding the circumference of certain 3-connected graphs. There is no good bound on the size of the largest bond (cocircuit) of a 3-connected graph, however. Oporowski, ...Oxley, and Thomas (J Combin Theory Ser B 57 (1993), 2, 239-257) proved the following result in 1993. For every positive integer k, there is an integer n =f (k ) such that every 3-connected graph with at least n vertices contains a W k- or K 3 ,k-minor. This result implies that the size of the largest bond in a 3-connected graph grows with the order of the graph. Oporowski et al. obtained a huge function f (k ) iteratively. In this article, we first improve the above authors' result and provide a significantly smaller and simpler function f (k ). We then use the result to obtain a lower bound for the largest bond of a 3-connected graph by showing that any 3-connected graph on n vertices has a bond of size at least 2 17 logn. In addition, we show the following: Let G be a 3-connected planar or cubic graph on n vertices. Then for any epsi >0, G has a W k-minor with k =Omega ((logn ) 1 -epsi ), and thus a bond of size at least Omega ((logn ) 1 -epsi ).
A fundamental theorem in graph theory states that any 3-connected graph contains a subdivision of K4. As a generalization, we ask for the minimum number of K4-subdivisions that are contained in every ...3-connected graph on n vertices. We prove that there are Ω(n3) such K4-subdivisions and show that the order of this bound is tight for infinitely many graphs. We further investigate a better bound in dependence on m and prove that the computational complexity of the problem of counting the exact number of K4-subdivisions is #P-hard.
There are numerous results bounding the circumference of certain 3‐connected graphs. There is no good bound on the size of the largest bond (cocircuit) of a 3‐connected graph, however. Oporowski, ...Oxley, and Thomas (J Combin Theory Ser B 57 (1993), 2, 239–257) proved the following result in 1993. For every positive integer k, there is an integer n=f(k) such that every 3‐connected graph with at least n vertices contains a Wk‐ or K3,k‐minor. This result implies that the size of the largest bond in a 3‐connected graph grows with the order of the graph. Oporowski et al. obtained a huge function f(k) iteratively. In this article, we first improve the above authors' result and provide a significantly smaller and simpler function f(k). We then use the result to obtain a lower bound for the largest bond of a 3‐connected graph by showing that any 3‐connected graph on n vertices has a bond of size at least 217logn. In addition, we show the following: Let G be a 3‐connected planar or cubic graph on n vertices. Then for any ε>0, G has a Wk‐minor with k=Ω((logn)1−ε), and thus a bond of size at least Ω((logn)1−ε).
A 3-connected graph is minimally 3-connected if removal of any edge destroys 3-connectivity. We present an algorithm for constructing minimally 3-connected graphs based on the results in (Dawes, JCTB ...40, 159-168, 1986) using two operations: adding an edge between non-adjacent vertices and splitting a vertex. To test sets of vertices and edges for 3-compatibility, which depends on the cycles of the graph, we develop a method for obtaining the cycles of G′ from the cycles of G, where G′ is obtained from G by one of the two operations above. We eliminate isomorphic duplicates using certificates generated by McKay’s isomorphism checker nauty. The algorithm consecutively constructs the non-isomorphic minimally 3-connected graphs with n vertices and m edges from the non-isomorphic minimally 3-connected graphs with n−1 vertices and m−2 edges, n−1 vertices and m−3 edges, and n−2 vertices and m−3 edges.
Fouquet and Jolivet conjectured that a
k
-connected graph of order
n
and independence number α ≥
k
has a cycle of length at least
Fouquet and Jolivet,
Problèmes combinatoires et théorie des graphes
...Orsay (1976), Problems, page 438. Here we prove this conjecture for k=3.
We show that for a given set
S of 2
n points in general position in the plane, there is a cubic 3-connected crossing-free geometric graph on the vertex set
S if and only if the interior of the convex ...hull of
S contains at least
n
−
1
points of
S. We also give similar results for sets of odd cardinality. Analogous partial results are given if the 3-connected crossing-free geometric graph is not required to be cubic.
S.C. Locke proposed a question: If
G
is a 3-connected graph with minimum degree
d
and
X
is a set of 4 vertices on a cycle in
G
, must
G
have a cycle through
X
with length at least
min
{
2
d
,
|
V
(
G
...)
|
}
? In this paper, we answer this question.
Let
G(
M)
be the family of all 3-connected graphs which can be embedded in a compact 2-manifold
M
with Euler characteristic
χ(
M)<0
. We have proved the following two results:
1.
Each graph
G∈
G(
M)
...having a
k-path, a path on
k-vertices,
k⩾4, contains a
k-path
P
k
such that its maximum degree
Δ
G
(
P
k
) in
G satisfies
Δ
G(P
k)⩽2+
(6k−6−2ϵ)
1+
|χ(
M)|
3
,
where
ϵ=0 for even
k and
ϵ=1 for odd
k. This bound is best possible.
2.
Each graph
G∈
G(
M)
of order at least
k⩾5 contains a connected subgraph
H of order
k such that its maximum degree
Δ
G
(
H) satisfies
Δ
G(H)⩽2+
(4k−2)
1+
|χ(
M)|
3
.
This bound is best possible.
The sharp values of
Δ
G
(
P
k
) and Δ
G
(
H) are determined for
k∈{2,3,4} as well.
Given two disjoint subsets
T
1
and
T
2
of nodes in a 3-connected graph
G
=
(
V
,
E
)
with a node set
V and an arc set
E, where
|
T
1
|
and
|
T
2
|
are even numbers, it is known that
V can be ...partitioned into two sets
V
1
and
V
2
such that the graphs induced by
V
1
and
V
2
are both connected and
|
V
1
∩
T
j
|
=
|
V
2
∩
T
j
|
=
|
T
j
|
/
2
holds for each
j
=
1
,
2
. An
O
(
|
V
|
2
log
|
V
|
)
time and
O
(
|
V
|
+
|
E
|
)
space algorithm for finding such a bipartition has been proposed based on a geometric argument, where
G is embedded in the plane
R
2
and the node set is bipartitioned by a ham-sandwich cut on the embedding. A naive implementation of the algorithm, however, requires high precision real arithmetic to distinguish two close points in a large set of points on
R
2
. In this paper, we propose an
O
(
|
V
|
2
)
time and space algorithm to the problem. The new algorithm, which remains to be based on the geometric embedding, can construct a solution purely combinatorially in the sense that it does not require computing actual embedded points in
R
2
and thereby no longer needs to store any real number for embedded points. Although the new algorithm seems to need more space complexity, it can be implemented only with
|
V
|
linked lists such that each element stores an integer in
1
,
|
V
|
.
Usually, for economic reasons, the physical infrastructure for transmission networks is designed as 2-connected graphs, i.e. interconnected rings. However, the increment of both, the traffic and the ...dependency of our professional and personal lives on ICT, demands more reliable transmission and distribution networks. Network interconnection problems are in general costly and complex to solve, categorized as NP-hard computational complexity. In addition, structural constraints such as 3-connectivity increase the time and resources utilized in the optimization search process. This paper presents and evaluates novel strategies in order to simplify the optimization process when planning the physical network interconnection as 3-connected with nodal degree 3. These strategies are applied in a case study and the results, using this and other approaches, are compared in terms of path distances, path length, network length, processing time, and number of iterations to find the solution.
PDF
