Raziskovalni matematični seminar  Arhiv
2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010 
1  2  3  4  5  6  7  8  9  10  11  12 
The repairing problem is a recently discovered combinatorial problem concerning Dyck words. We have first identified the repairing problem when studying an open question in automata theory, the complexity of translation of onecounter automata (OCA) on finite words into Parikhequivalent nondeterministic finite automata (NFA). But it appears that the repairing problem has natural connections with other combinatorial problems arising in analysis of weak models of computation (e.g., blackandwhite pebble games). We hope that more relations will be discovered in future.
In the talk I will define the problem and give a survey of known results about it.
This is joint work with D. Chistikov.
Join Zoom Meeting Here!
A vertex in a graph is avoidable if every induced path on three vertices with middle vertex is contained in an induced cycle. Dirac's classical result from 1961 on the existence of simplicial vertices in chordal graphs is equivalent to the statement that every chordal graph has an avoidable vertex. Beisegel, Chudovsky, Gurvich, Milani\v{c}, and Servatius (2019) generalized the notion of avoidable vertices to \emph{avoidable paths}, and conjectured that every graph that contains an induced vertex path also contains an avoidable induced vertex path; they proved the result for . The case was known much earlier, due to a work of Ohtsuki, Cheung, and Fujisawa in 1976. The conjecture was proved for all in 2020 by Bonamy, Defrain, Hatzel, and Thiebaut. This result generalizes the mentioned results regarding avoidable vertices, as well as a result by Chv\'atal, Rusu, and Sritharan (2002) suggested by West on the existence of simplicial vertex paths in graphs excluding induced cycles of length at least .
In this talk we discuss an adaptation of the approach by Bonamy et al.~from a reconfiguration point of view. We say that two induced vertex paths are \emph{shifts} of each other if their union is an induced path with vertices and show that in every graph, every induced path can be shifted to an avoidable one. We also present an analogous result about paths that are not necessarily induced, where an efficient reconfiguration sequence relies on the properties of depthfirst search trees.
Join Zoom Meeting Here!
Let G denote a distancebiregular graph with bipartite parts Y and Y’. Let D denote the eccentricity of vertices in Y. Given a vertex z, let \Gamma_i(z) denote the set of all vertices which are at distance i from z. For vertices x and y, let \Gamma_{i,j}(x,y) denote the collection of all vertices which are at distance i from x and at distance j from y.
In this talk, we will show necessary and sufficient conditions on the intersection array of G for which the given graph has one of the following two combinatorial structures:

for all i (1 \leq i \leq D2) and for all x\in Y, y\in \G_2(x) and z \in \G_{i,i}(x,y) the number of vertices in \G_{1,1}(x,y) which are at distance i1 from z is independent of the choice of x,y and z.

for all i (1 \leq i \leq D1) and for all x\in Y, y\in \G_2(x) and z \in \G_{i,i}(x,y) the number of vertices in \G_{1,1}(x,y) which are at distance i1 from z is independent of the choice of x,y and z.
Distancebiregular graphs with the previous combinatorial structures are called almost 2Yhomogeneous and 2Yhomogeneous, respectively. Several examples will also be presented. This is joint work with Safet Penjić.
Let G=(V,E) be a finite undirected graph with vertex set V(G) of order V(G)=n and edge set E(G) of size E(G)=m. Let d_{1}\geq d_{2}\geq...\geq d_{n} be the degree sequence of the graph G.
A clique in a graph G is a complete subgraph of G. A clique is called maximum if it has maximum cardinality.
The clique number of a graph G, denoted \omega(G), is the order of a maximum clique of G.
In 1907 Mantel proved that a trianglefree graph with n vertices can contain at most $lfloor \frac{n^{2}}{4}\rfloor edges. In 1941 Tur\' an generalized Mantel's result to graphs not containing cliques of size r by proving that graphs of order n that contain no induced K_{r} have at most (1\frac{1}{r1}) \frac{n^{2}}{2} edges.
In this talk, we present new lower bounds for the clique number \omega(G). Moreover, we obtain a new bound for the maximum number of edges in a K_{r}free graph G of order n, with minimum degree d_{n}, and
maximum degree d_{1}.
The results are based on elementary inequalities applied to the degree sequence d_{1}\geq d_{2}\geq\ldots \geq d_{n}.
We are looking forward to meeting at the video conference.
Join Zoom Meeting HERE!
In the literature, one can find at least three different genus parameters associated with a finite group: genus, symmetric genus, and strong symmetric genus. While the genus of a group is defined in terms of the (undirected, nonedgecolored) Cayley graphs, plain graphs are not adequate for modeling symmetric and strongly symmetric embeddings and thus cannot be used directly for determining the symmetric and strong symmetric genus of a group. We propose (generalized) action graphs to model such embeddings. Although action graphs are a wider class of edgecolored, partially directed graphs than Cayley color (di)graphs, the idea of symmetric and strongly symmetric embedding can be applied to them. In addition, we present some applications of action graphs.
This is joint work with Thomas W. Tucker.
We are looking forward to meeting at the videoconference.
Join Zoom Meeting HERE!
For more info visit our YouTube Channel.