20.500.12556/RUP-23108 Extremal totally regular mixed graphs and partially oriented incidence graphs of projective and biaffine planes An (r, z; g)-mixed graph is a graph containing both edges and darts satisfying the regularity property that each vertex of the graph is incident to r edges, z ingoing and z outgoing darts (called total regularity), and being of oriented girth g, i.e., containing an oriented cycle of length g, and no shorter oriented cycles. The problem addressed in this paper is analogous to the Cage Problem and calls for determining the orders of the smallest totally regular (r, z; g)-mixed graphs. We derive several upper and lower bounds on the orders of such minimal graphs, study the relations between these extremal graphs and their non-oriented or digraphical counterparts, and focus on properties of totally regular mixed graphs obtained by replacing some of the edges of the incidence graphs of projective and biaffine planes by darts. We also introduce two constructions based on introducing additional edges or darts into induced subgraphs of these incidence graphs. Graf (r,z;g)-mešanega tipa je graf, ki vsebuje tako povezave (neusmerjene povezave) kot loke (usmerjene povezave) ter zadošča pogoju regularnosti, da je vsak incidenten z r povezavami, z vhodnimi in z izhodnimi loki (t. i. popolna regularnost). Graf ima usmerjeni obseg g, kar pomeni, da vsebuje usmerjeni cikel dolžine g, ne vsebuje pa nobenega krajšega usmerjenega cikla. Problem, obravnavan v tem članku, je analogen problemu kletke (Cage Problem) in se nanaša na določitev reda najmanjših popolnoma regularnih (r,z;g)-mešanih grafov. Izpeljemo več zgornjih in spodnjih mej za rede takšnih minimalnih grafov, preučimo povezave med temi ekstremalnimi grafi in njihovimi neusmerjenimi oziroma digrafskimi ustrezniki ter se osredotočimo na lastnosti popolnoma regularnih mešanih grafov, dobljenih z zamenjavo nekaterih povezav v incidenčnih grafih projektivnih in biafinih ravnin z loki. Poleg tega predstavimo dve konstrukciji, ki temeljita na dodajanju novih povezav ali lokov v inducirane podgrafe teh incidenčnih grafov. totally regular mixed graph girth projective plane biaffine plane popolnoma regularen mešani graf obseg grafa projektivna ravnina biafina ravnina true false true Angleški jezik Slovenski jezik Članek v reviji 2026-06-04 15:07:24 2026-06-04 15:07:28 2026-06-06 03:05:37 0000-00-00 00:00:00 2025 0 0 str. 1-19 Vol. 2025 0000-00-00 PostprintKoncna NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 0218-0006 10.1007/s00026-025-00788-5 280518403 RAZ_Bagin_Jajcay_Tatiana_2025.pdf RAZ_Bagin_Jajcay_Tatiana_2025.pdf 1 EC001DB3F6C5C07B4326B7EA118BC9C4 8c54202fdd1d8e4959e0b227ccdd933063628583bfb7fbe3a47caf1e98257920 5493b4b8-6016-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=33759 https://link.springer.com/article/10.1007/s00026-025-00788-5 1 37160b02-6016-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=33758 Fakulteta za matematiko, naravoslovje in informacijske tehnologije 0 0 0