Naslov
Filling of a given boundary by p-gons and related problems

Autori
Dutour Sikirić, Mathieu ; Deza, Michel ; Shtogrin, Mikhail

Izvornik
Discrete applied mathematics (0166-218X) 156 (2008), 9; 1518-1535

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
plane graphs ; enumeration

Sažetak
We consider here (p, s)-polycycles (3 <= p <= s) i.e. plane graphs, such that all interior faces are p-gons, all interior vertices are s-valent and any vertex of the boundary (i.e. the exterior face) has valency within [2, s]. The boundary sequence of a (p, s)-polycycle P is the sequence b(P) enumerating, up to a cyclic shift or reversal, the consecutive valencies of vertices of the boundary. We show that the values p=3, 4 are the only ones, such that the boundary sequence defines its (p, 3)-filling (i.e. a (p, 3)-polycycle with given boundary) uniquely. Also we give new results in the enumeration of maps Mn(p, q) (i.e. plane 3-valent maps with only p- and q-gonal faces, such that the q-gons are organized in an n-ring) and two of their generalizations. Both problems are similar (3-valent filling by p-gons of a boundary or of a ring of q-gons) and the same programs were used for both computations.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA