1. Mutually avoiding Eulerian circuitsGrahame Erskine, Terry S. Griggs, Robert Lewis, James Tuite, 2026, izvirni znanstveni članek Opis: Two Eulerian circuits, both starting and ending at the same vertex, are avoiding if at every other point of the circuits they are at least distance 2 apart. An Eulerian graph which admits two such avoiding circuits starting from any vertex is said to be doubly Eulerian. The motivation for this definition is that the extremal Eulerian graphs, i.e. the complete graphs on an odd number of vertices and the cycles, are not doubly Eulerian. We prove results about doubly Eulerian graphs and identify those that are the “densest” and “sparsest” in terms of the number of edges.
Ključne besede: Eulerian circuit, avoidance
Objavljeno v RUP: 20.08.2026; Ogledov: 218; Prenosov: 6
 Celotno besedilo (359,50 KB) |
2. On bipartite (1,1,k)-mixed graphsCristina Dalfó, Grahame Erskine, Geoffrey Exoo, Miquel Àngel Fiol, James Tuite, 2025, izvirni znanstveni članek Opis: Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are bipartite and in which the undirected and directed degrees are one. The best graphs, in terms of the number of vertices, are presented for small diameters. Moreover, two infinite families of such graphs with diameter k and number of vertices of the order of 2k/2 are proposed, one of them being totally regular (1,1)-mixed graphs. In addition, we present two more infinite families called chordal ring and chordal double ring mixed graphs, which are bipartite and related to tessellations of the plane. Finally, we give an upper bound that improves the Moore bound for bipartite mixed graphs for r = z = 1.
Ključne besede: mixed graph, degree/diameter problem, Moore bound, bipartite graph
Objavljeno v RUP: 03.11.2025; Ogledov: 1445; Prenosov: 8
Celotno besedilo (628,98 KB) |
3. On some extremal position problems for graphsJames Tuite, Elias John Thomas, Ullas Chandran S.V., 2025, izvirni znanstveni članek Opis: The general position number of a graph G is the size of the largest set of vertices S such that no geodesic of G contains more than two elements of S. The monophonic position number of a graph is defined similarly, but with `induced path' in place of `geodesic'. In this paper we investigate some extremal problems for these parameters. Firstly we discuss the problem of the smallest possible order of a graph with given general and monophonic position numbers. We then determine the asymptotic order of the largest size of a graph with given general or monophonic position number, classifying the extremal graphs with monophonic position number two. Finally we establish the possible diameters of graphs with given order and monophonic position number.
Ključne besede: general position, monophonic position, Turán problems, size, diameter, induced path
Objavljeno v RUP: 21.10.2025; Ogledov: 744; Prenosov: 11
Celotno besedilo (396,13 KB) |
