Canadian Mathematical Society
Canadian Mathematical Society
  location:  Publicationsjournals
Search results

Search: MSC category 05C10 ( Planar graphs; geometric and topological aspects of graph theory [See also 57M15, 57M25] )

  Expand all        Collapse all Results 1 - 8 of 8

1. CJM Online first

McDiarmid, Colin; Wood, David R.
Edge-Maximal Graphs on Surfaces
We prove that for every surface $\Sigma$ of Euler genus $g$, every edge-maximal embedding of a graph in $\Sigma$ is at most $O(g)$ edges short of a triangulation of $\Sigma$. This provides the first answer to an open problem of Kainen (1974).

Keywords:graph, surface, embedding

2. CJM 2014 (vol 66 pp. 1327)

Mohar, Bojan; Skoda, Petr
Obstructions of Connectivity Two for Embedding Graphs into the Torus
The complete set of minimal obstructions for embedding graphs into the torus is still not determined. In this paper, we present all obstructions for the torus of connectivity 2. Furthermore, we describe the building blocks of obstructions of connectivity 2 for any orientable surface.

Keywords:torus, obstruction, minor, connectivity 2
Categories:05C10, 05C83

3. CJM 2010 (vol 62 pp. 1058)

Chen, Yichao; Liu, Yanpei
On a Conjecture of S. Stahl
S. Stahl conjectured that the zeros of genus polynomials are real. In this note, we disprove this conjecture.

Keywords:genus polynomial, zeros, real

4. CJM 2009 (vol 61 pp. 1300)

Hubard, Isabel; Orbani\'c, Alen; Weiss, Asia Ivi\'c
Monodromy Groups and Self-Invariance
For every polytope $\mathcal{P}$ there is the universal regular polytope of the same rank as $\mathcal{P}$ corresponding to the Coxeter group $\mathcal{C} =[\infty, \dots, \infty]$. For a given automorphism $d$ of $\mathcal{C}$, using monodromy groups, we construct a combinatorial structure $\mathcal{P}^d$. When $\mathcal{P}^d$ is a polytope isomorphic to $\mathcal{P}$ we say that $\mathcal{P}$ is self-invariant with respect to $d$, or $d$-invariant. We develop algebraic tools for investigating these operations on polytopes, and in particular give a criterion on the existence of a $d$\nobreakdash-auto\-morphism of a given order. As an application, we analyze properties of self-dual edge-transitive polyhedra and polyhedra with two flag-orbits. We investigate properties of medials of such polyhedra. Furthermore, we give an example of a self-dual equivelar polyhedron which contains no polarity (duality of order 2). We also extend the concept of Petrie dual to higher dimensions, and we show how it can be dealt with using self-invariance.

Keywords:maps, abstract polytopes, self-duality, monodromy groups, medials of polyhedra
Categories:51M20, 05C25, 05C10, 05C30, 52B70

5. CJM 2008 (vol 60 pp. 960)

Stahl, Saul
Erratum: On the Zeros of Some Genus Polynomials
No abstract.

Categories:05C10, 05A15, 30C15, 26C10

6. CJM 2008 (vol 60 pp. 958)

Chen, Yichao
A Note on a Conjecture of S. Stahl
S. Stahl (Canad. J. Math. \textbf{49}(1997), no. 3, 617--640) conjectured that the zeros of genus polynomial are real. L. Liu and Y. Wang disproved this conjecture on the basis of Example 6.7. In this note, it is pointed out that there is an error in this example and a new generating matrix and initial vector are provided.

Keywords:genus polynomial, zeros, real
Categories:05C10, 05A15, 30C15, 26C10

7. CJM 1997 (vol 49 pp. 617)

Stahl, Saul
On the zeros of some genus polynomials
In the genus polynomial of the graph $G$, the coefficient of $x^k$ is the number of distinct embeddings of the graph $G$ on the oriented surface of genus $k$. It is shown that for several infinite families of graphs all the zeros of the genus polynomial are real and negative. This implies that their coefficients, which constitute the genus distribution of the graph, are log concave and therefore also unimodal. The geometric distribution of the zeros of some of these polynomials is also investigated and some new genus polynomials are presented.

Categories:05C10, 05A15, 30C15, 26C10

8. CJM 1997 (vol 49 pp. 193)

Casali, Maria Rita
Classifying PL $5$-manifolds by regular genus: the boundary case
In the present paper, we face the problem of classifying classes of orientable PL $5$-manifolds $M^5$ with $h \geq 1$ boundary components, by making use of a combinatorial invariant called {\it regular genus} ${\cal G}(M^5)$. In particular, a complete classification up to regular genus five is obtained: $${\cal G}(M^5) = \gG \leq 5 \Longrightarrow M^5 \cong \#_{\varrho - \gbG}(\bdo) \# \smo_{\gbG},$$ where $\gbG = {\cal G}(\partial M^5)$ denotes the regular genus of the boundary $\partial M^5$ and $\smo_{\gbG}$ denotes the connected sum of $h\geq 1$ orientable $5$-dimensional handlebodies $\cmo_{\alpha_i}$ of genus $\alpha_i\geq 0$ ($i=1,\ldots, h$), so that $\sum_{i=1}^h \alpha_i = \gbG.$ \par Moreover, we give the following characterizations of orientable PL $5$-manifolds $M^5$ with boundary satisfying particular conditions related to the ``gap'' between ${\cal G}(M^5)$ and either ${\cal G}(\partial M^5)$ or the rank of their fundamental group $\rk\bigl(\pi_1(M^5)\bigr)$: $$\displaylines{{\cal G}(\partial M^5)= {\cal G}(M^5) = \varrho \Longleftrightarrow M^5 \cong \smo_{\gG}\cr {\cal G}(\partial M^5)= \gbG = {\cal G}(M^5)-1 \Longleftrightarrow M^5 \cong (\bdo) \# \smo_{\gbG}\cr {\cal G}(\partial M^5)= \gbG = {\cal G}(M^5)-2 \Longleftrightarrow M^5 \cong \#_2 (\bdo) \# \smo_{\gbG}\cr {\cal G}(M^5) = \rk\bigl(\pi_1(M^5)\bigr)= \varrho \Longleftrightarrow M^5 \cong \#_{\gG - \gbG}(\bdo) \# \smo_{\gbG}.\cr}$$ \par Further, the paper explains how the above results (together with other known properties of regular genus of PL manifolds) may lead to a combinatorial approach to $3$-dimensional Poincar\'e Conjecture.

Categories:57N15, 57Q15, 05C10

© Canadian Mathematical Society, 2017 :