This paper uses combinatorial group theory to help answer some long-standing questions about the genera of orientable surfaces that carry particular kinds of regular maps. By classifying all orientably-regular maps whose automorphism group has order coprime to $g-1$, where $g$ is the genus, all orientably-regular maps of genus $p+1$ for $p$ prime are determined. As a consequence, it is shown that orientable surfaces of infinitely many genera carry no regular map that is chiral (irreflexible), and that orientable...

For two vertices u and v of a connected graph G, the set $I_G[u,v]$ consists of all those vertices lying on u-v geodesics in G. Given a set S of vertices of G, the union of all sets $I_G[u,v]$ for u,v ∈ S is denoted by $I_G\left[S\right]$. A set S ⊆ V(G) is a geodetic set if $I_G\left[S\right]=V\left(G\right)$ and the minimum cardinality of a geodetic set is its geodetic number g(G) of G. Bounds for the geodetic number of strong product graphs are obtainted and for several classes improved bounds and exact values are obtained.

Alon and Tarsi presented in a previous paper a certain weighted sum over the set of all proper $k$-colorings of a graph, which can be computed from its graph polynomial. The subject of this paper is another combinatorial interpretation of the same quantity, expressed in terms of the numbers of certain modulo $k$ flows in the graph. Some relations between graph parameters can be obtained by combining these two formulas. For example: The number of proper 3-colorings of a 4-regular graph and the number...

The Gutman index and the edge-Wiener index have been extensively investigated particularly in the last decade. An important stream of re- search on graph indices is to bound indices in terms of the order and other parameters of given graph. In this paper we present asymptotically sharp upper bounds on the Gutman index and the edge-Wiener index for graphs of given order and vertex-connectivity κ, where κ is a constant. Our results substantially generalize and extend known results in the area.

If $G$ is a connected graph of order $n\ge 1$, then by a hamiltonian coloring of $G$ we mean a mapping $c$ of $V\left(G\right)$ into the set of all positive integers such that $|c\left(x\right)-c\left(y\right)|\ge n-1-D_G(x,y)$ (where $D_G(x,y)$ denotes the length of a longest $x-y$ path in $G$) for all distinct $x,y\in V\left(G\right)$. Let $G$ be a connected graph. By the hamiltonian chromatic number of $G$ we mean $$min(max(c\left(z\right);z\in V\left(G\right)\left)\right),$$ where the minimum is taken over all hamiltonian colorings $c$ of $G$. The main result of this paper can be formulated as follows: Let $G$ be a connected graph of order $n\ge 3$. Assume that there exists a subgraph...

For a connected graph G with at least two vertices and S a subset of vertices, the convex hull ${\left[S\right]}_G$ is the smallest convex set containing S. The hull number h(G) is the minimum cardinality among the subsets S of V(G) with ${\left[S\right]}_G=V\left(G\right)$. Upper bound for the hull number of strong product G ⊠ H of two graphs G and H is obtainted. Improved upper bounds are obtained for some class of strong product graphs. Exact values for the hull number of some special classes of strong product graphs are obtained. Graphs G and H...

An i-chord of a cycle or path is an edge whose endpoints are a distance i ≥ 2 apart along the cycle or path. Motivated by many standard graph classes being describable by the existence of chords, we investigate what happens when i-chords are required for specific values of i. Results include the following: A graph is strongly chordal if and only if, for i ∈ {4,6}, every cycle C with |V(C)| ≥ i has an (i/2)-chord. A graph is a threshold graph if and only if, for i ∈ {4,5}, every path P with |V(P)|...