Constructions of Large Graphs on Surfaces Feria-Puron, Ramiro; Pineda-Villavicencio, Guillermo
Graphs and combinatorics,
07/2014, Letnik:
30, Številka:
4
Journal Article
Recenzirano
Odprti dostop
We consider the degree/diameter problem for graphs embedded in a surface, namely, given a surface Σ and integers Δ and
k
, determine the maximum order
N
(Δ,
k
,Σ) of a graph embeddable in Σ with ...maximum degree Δ and diameter
k
. We introduce a number of constructions which produce many new largest known planar and toroidal graphs. We record all these graphs in the available tables of largest known graphs. Given a surface Σ of Euler genus
g
and an odd diameter
k
, the current best asymptotic lower bound for
N
(Δ,
k
,Σ) is given by
Our constructions produce new graphs of order
thus improving the former value.
We give a polynomial-time algorithm to find a shortest contractible cycle (i.e., a closed walk without repeated vertices) in a graph embedded in a surface. This answers a question posed by ...Hutchinson. In contrast, we show that finding a shortest contractible cycle through a given vertex is NP-hard. We also show that finding a shortest separating cycle in an embedded graph is NP-hard. This answers a question posed by Mohar and Thomassen.
The recent paper ‘Linear connectivity forces large complete bipartite minors’ by Böhme, Kawarabayashi, Maharry and Mohar relies on an extension of Robertson and Seymourʼs structure theorem for graphs ...with a forbidden minor. We describe a more direct approach which uses just the original structure theorem.
Let
a be an integer. It is proved that for any
s and
k, there exists a constant
N
=
N
(
s
,
k
,
a
)
such that every
31
2
(
a
+
1
)
-connected graph with at least
N vertices either contains a ...subdivision of
K
a
,
s
k
or a minor isomorphic to
s disjoint copies of
K
a
,
k
. In fact, we prove that connectivity
3
a
+
2
and minimum degree at least
31
2
(
a
+
1
)
−
3
are enough while the other conditions cannot be weakened.
When
s
=
1
and
k
=
a
, this implies that every
31
2
(
a
+
1
)
-connected graph with at least
N
(
a
)
vertices has a
K
a
-minor. This is the first result where a linear lower bound on the connectivity in terms of the parameter
a forces a
K
a
-minor. This resolves a conjecture proposed by Mader W. Mader, Existenz
n-fach zusammenhängender Teilgraphen in Graphen genügend grosser Kantendichte, Abh. Math. Sem. Univ. Hamburg 37 (1972) 86–97 and Thomason A. Thomason, An extremal function for contractions of graphs, Math. Proc. Cambridge Philos. Soc. 95 (1984) 261–265; A. Thomason, The extremal function for complete minors, J. Combin. Theory Ser. B 81 (2001) 318–338. Our result also generalizes a recent result of Böhme and Kostochka T. Böhme, A. Kostochka, Disjoint
K
r
-minors in large graphs with given average degree, European J. Combin. 26 (2005) 289–292, resolves a conjecture of Fon-Der-Flaass D. Fon-Der-Flaass, private communication, and has several other consequences.
A graph parameter is
self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph by more than a constant factor. Self-duality has been examined for ...several width parameters, such as branchwidth, pathwidth, and treewidth. In this paper, we give a direct proof of the self-duality of branchwidth in graphs embedded in some surface. In this direction, we prove that
bw
(
G
∗
)
≤
6
⋅
bw
(
G
)
+
2
g
−
4
for any graph
G
embedded in a surface of Euler genus
g
.
► A graph parameter is
self-dual in a class of graphs embeddable in a surface if its value does not change in the dual graph by more than a constant factor. ► Self-duality has been examined for several width parameters, such as branchwidth, pathwidth, and treewidth. ► In this paper, we give a direct proof of the self-duality of branchwidth in graphs embedded in some surface. ► Namely, we prove that
bw
(
G
∗
)
≤
6
⋅
bw
(
G
)
+
2
g
−
4
for any graph
G
embedded in a surface of Euler genus
g
.
Let
P
¯
be a sequence of length 2
n in which each element of
{
1
,
2
,
…
,
n
}
occurs twice. Let
P
′
be a closed curve in a closed surface
S having
n points of simple self-intersections, inducing a ...4-regular graph embedded in
S which is 2-face colorable. If the sequence of auto-intersections along
P
′
is given by
P
¯
, we say that
P
′
is a 2-face colorable solution for the Gauss code
P
¯
on surface
S or a lacet for
P
¯
on
S. In this paper we show (by using surface homology theory mod 2), that the set of lacets for
P
¯
on
S are in 1–1 correspondence with the tight solutions of a system of quadratic equations over the Galois field
GF
(
2
)
. If
S is the 2-sphere, the projective plane or the Klein bottle, the corresponding quadratic systems are equivalent to linear ones. In consequence, algorithmic characterizations for the existence of solutions on these surfaces are available. For the two first surfaces this produces simple proofs of known results. The algorithmic characterization for the existence of solutions on the Klein bottle is new. We provide a polynomial algorithm to resolve the issue.
6-Critical Graphs on the Klein Bottle Kawarabayashi, Ken-ichi; Král', Daniel; Kynčl, Jan ...
SIAM journal on discrete mathematics,
01/2009, Letnik:
23, Številka:
1
Journal Article
Recenzirano
We provide a complete list of 6-critical graphs that can be embedded on the Klein bottle settling a problem of Thomassen J. Combin. Theory Ser. B, 70 (1997), pp. 67-100, Problem 3. The list consists ...of nine nonisomorphic graphs which have altogether 18 nonisomorphic 2-cell embeddings and one embedding that is not 2-cell.
Celotno besedilo
Dostopno za:
CEKLJ, DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
PDF
