ON THE GENUS OF RANDOM-REGULAR GRAPHS Lucas Blakeslee Abstract

2025-05-02 0 0 205.38KB 4 页 10玖币

侵权投诉

ON THE GENUS OF RANDOM-REGULAR GRAPHS

Lucas Blakeslee

Abstract

The genus of a graph is a topological invariant that measures the minimum genus of a surface on

which the graph can be embedded without any edges crossing. Graph genus plays a fundamental role

in topological graph theory, used to classify and study diﬀerent types of graphs and their properties.

We show that, for any integer d≥2, the genus of a random d-regular graph on nnodes is (d−2)

4n(1−ε)

with high probability for any ε > 0.

1 Introduction

Topological graph theory is a branch of mathematics that studies the topological properties of graphs

and their embeddings on surfaces. It combines techniques from topology, algebraic geometry, and

combinatorics to study the structure and properties of graphs. This ﬁeld of mathematics is particu-

larly useful for understanding the global properties of graphs, such as connectivity, and for studying

the way in which graphs can be embedded in the plane or in more complicated topological spaces.

One central concept in topological graph theory is that of graph genus. The classiﬁcation theorem

for compact surfaces, ﬁrst proposed by M¨obius in the early 1860s [12] (though not proved rigorously

until the 1920s by Brahana [8]), states that all closed surfaces are homeomorphic to spheres with

some number of handles or crosscaps attached. We denote a sphere with ghandles attached Sg.

This gis called the genus of the surface. The orientable genus of a graph G,γ(G), is a topological

invariant denoting the smallest number gsuch that Gcan be drawn onto the orientable surface Sg

without any edge crossings. In the simplest case, a graph with genus 0 — i.e., a planar graph —

can be drawn on the plane without edge crossings. A graph of genus 1 can be drawn without edge

crossings on a torus, a graph of genus 2 on a surface with two handles, and so forth.

Much of the literature in topological graph theory focuses on the study of the embeddings of

certain families of graphs, such as complete graphs [13], wheel graphs [10], and complete bipartite

(and more generally, k-partite) graphs [7, 5], to name a few. Many graph problems, such as the

problem of ﬁnding a maximal independent set, ﬁnding a minimum t-spanner, the sparsest-cut prob-

lem, and several constraint satisfaction problems, are NP-hard for graphs of genus greater than zero

[4, 1, 11, 9]. Therefore, the genus of a graph can be an important measure of complexity in analyzing

the eﬃciency of graph algorithms. Determining the genus of an arbitrary graph is hard, however. In

fact, we know the graph genus problem to be NP-complete [14].

The goal of this paper is to characterize the growth of the typical genus of a random regular

graph, which can range from 0 in the case of planar graphs to the genus of the complete graph Kn,

l(n−3)(n−4)

12 m, as per [13]. Related work has been performed by Asplund et al. [3], who investigate

the so-called k-planar crossing number of random regular graphs, another metric of how “distant”

a graph is from being planar; however, the k-planar crossing number of a graph and its genus can

be arbitrarily far apart. Additionally, Archdeacon and Grable have showed that the genus of the

Erd˝os-R´enyi graph grows as n2

24 [2]. However, as we show here, the genus of a random d-regular

graph grows with high probability as d−2

4nwhere nis the number of nodes.

2 Results

We begin by bounding the number of cycles on the graph, which provides a bound on the number of

faces, which in turn can then be used in conjunction with Euler’s formula to describe the asymptotic

growth of the genus. We say that an event occurs with high probability (w.h.p.) if it’s probability

arXiv:2210.15162v2 [math.CO] 30 Jan 2023

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ONTHEGENUSOFRANDOM-REGULARGRAPHSLucasBlakesleeAbstractThegenusofagraphisatopologicalinvariantthatmeasurestheminimumgenusofasurfaceonwhichthegraphcanbeembeddedwithoutanyedgescrossing.Graphgenusplaysafundamentalroleintopologicalgraphtheory,usedtoclassifyandstudydierenttypesofgraphsandtheirproperties....

展开>> 收起<<

ON THE GENUS OF RANDOM-REGULAR GRAPHS Lucas Blakeslee Abstract.pdf

共4页,预览1页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

ON THE GENUS OF RANDOM-REGULAR GRAPHS Lucas Blakeslee Abstract

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: