414 KB56 KB200820252019Potočnik, PrimožVidali, Janošletnik:17številka:2str. 349-368ISSN:1855-3966COBISSID_HOST:18803545URN:URN:NBN:SI:doc-RB0X46ZHenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneacubicgirthgirth-regulargrafgraphkubični grafiožinaožinska regularnostGirth-regular graphs|We introduce a notion of a girth-regular graph as a ?$k$?-regular graph for which there exists a non-descending sequence ?$(a_1, a_2, \dots , a_k)$? (called the signature) giving, for every vertex ?$u$? of the graph, the number of girth cycles the edges with end-vertex ?$u$? lie on. Girth-regularity generalises two very different aspects of symmetry in graph theory: that of vertex transitivity and that of distance-regularity. For general girth-regular graphs, we give some results on the extremal cases of signatures. We then focus on the cubic case and provide a characterisation of cubic girth-regular graphs of girth up to 5Ožinsko regularne grafe definiramo kot ?$k$?-regularne grafe, za katere obstaja nepadajo če zaporedje ?$(a_1, a_2, \dots , a_k)$? (imenovano podpis), ki za vsako vozlišče ?$u$? v grafu pove, v koliko ožinskih ciklih (tj. ciklih najmanjše dolžine) ležijo povezave s krajiščem v vozlišču ?$u$?. Ožinska regularnost posplošuje dva zelo različna vidika simetrije v teoriji grafov: vozliščno tranzitivnost in razdaljno regularnost. Za splošne ožinsko regularne grafe podamo nekaj rezultatov o ekstremalnih primerih podpisa. Nato se osredotočimo na kubične ožinsko regularne grafe, za katere podamo karakterizacijo v primeru, ko je ožina največ 5TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije