1. Enumerating runs, valleys, and peaks in Catalan wordsJean-Luc Baril, Pamela Harris, Kimberly Harry, Matt McClinton, José L. Ramírez, 2025, original scientific article Abstract: We provide generating functions, formulas, and asymptotic expressions for the number of Catalan words based on the number of runs of ascents (descents), runs of weak ascents (descents), l-valleys, valleys, symmetric valleys, l-peaks, peaks, and symmetric peaks. We also establish some bijections with restricted Dyck paths and ordered trees that transports some statistics.
Keywords: Catalan word, generating function, combinatorial statistic, Dyck path
Published in RUP: 03.11.2025; Views: 63; Downloads: 0
 Full text (442,69 KB) |
2. On some extremal position problems for graphsJames Tuite, Elias John Thomas, Ullas Chandran S.V., 2025, original scientific article Abstract: 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.
Keywords: general position, monophonic position, Turán problems, size, diameter, induced path
Published in RUP: 21.10.2025; Views: 107; Downloads: 0
Full text (396,13 KB) |
3. |
4. On the metric subgraphs of a graphYanan Hu, Xingzhi Zhan, 2025, original scientific article Abstract: The three subgraphs of a connected graph induced by the center, annulus and periphery are called its metric subgraphs. The main results are as follows. (1) There exists a graph of order n whose metric subgraphs are all paths if and only if n ≥ 13 and the smallest size of such a graph of order 13 is 22; (2) there exists a graph of order n whose metric subgraphs are all cycles if and only if n ≥ 15, and there are exactly three such graphs of order 15; (3) for every integer k ≥ 3, we determine the possible orders for the existence of a graph whose metric subgraphs are all connected k-regular graphs; (4) there exists a graph of order n whose metric subgraphs are connected and pairwise isomorphic if and only if n ≥ 24 and n is divisible by 3. An unsolved problem is posed.
Keywords: center, annulus, periphery, metric subgraphs, path, cycle
Published in RUP: 16.09.2025; Views: 177; Downloads: 5
Full text (533,77 KB)
This document has more files! More... |
5. Avoidable vertices and edges in graphsJesse Beisegel, Maria Chudnovsky, Vladimir Gurvich, Martin Milanič, Mary Agnes Milanič, 2019, published scientific conference contribution Keywords: simplicial vertex, avoidable vertex, avoidable edge, avoidable path, maximum weight clique problem, polynomial-time algorithm, hole-cyclically orientable graph
Published in RUP: 20.08.2019; Views: 3443; Downloads: 161
 Link to full text |
6. |
7. Nove karakterizacije v strukturni teoriji grafov : 1-popolno usmerljivi grafi, produktni grafi in cena povezanostiTatiana Romina Hartinger, 2017, doctoral dissertation Keywords: 1-perfectly orientable graph, structural characterization of families of graphs, chordal graph, interval graph, circular arc graph, cograph, block-cactus graph, cobipartite graph, K4-minor-free graph, outerplanar graph, graph product, Cartesian product, lexicographic product, direct product, strong product, price of connectivity, cycle transversal, path transversal
Published in RUP: 09.11.2017; Views: 5128; Downloads: 44
Link to full text |
8. |
9. |
10. |
