Raziskovalni matematični seminar - Arhiv

Canonical bipartite double cover of a graph $X$ is defined to be the graph $BX \coloneqq X\times K_2$. The group $\Aut X\times S_2$ naturally appears as a subgroup of $\Aut BX$. In case $\Aut BX \cong \Aut X \times S_2$, the graph $X$ is called stable. Otherwise, it is unstable. If $X$ is additionally connected, non-bipartite and distinct vertices have distinct sets of neighbors, it is called non-trivially unstable. The behavior of $\Aut(X\times Y)$, with $X$ non-bipartite and $Y$ bipartite, heavily depends on the particular case of $\Aut BX$, where we take $Y=K_2$.

Known results about stability of Cayley graphs on cyclic (and more generally, abelian) groups of odd order are discussed. Circulant graphs are Cayley graphs of cyclic groups. In his work on symmetries of unstable graphs, Steve Wilson introduced several conditions implying instability of circulants of even order, referred to as Wilson types in the literature. It has also been conjectured that these conditions can explain all instability in circulant graphs.

Corrections, both old and new, and generalizations of Wilson types are discussed. In addition to revisiting already known counterexamples to the conjecture, obtained results are used to construct new infinite families of counterexamples. It is established that every non-trivially unstable circulant of order $2p$, $p$ an odd prime, has a Wilson type. It is also established that the same holds for every non-trivially unstable circulant of valency at most $7$.

This is joint work with Ademir Hujdurović and Dave Witte Morris.

Join the Zoom Meeting Here.

See you there!

Everyone is welcome and encouraged to attend.

Let $\Gamma$ be a graph with vertex set $V$, and let $n=|V|$. A distance magic labeling of $\Gamma$ is a bijection $\ell : V \mapsto \{1,2, \ldots, n\}$ for which there exists a positive integer $r$ such that $\sum_{y \in \Gamma(x)} \ell(y) = r$ for all vertices $y \in V$, where $\Gamma(x)$ is the neighborhood of $x$. A graph is said to be distance magic if it admits a distance magic labeling. In this talk I will discuss tetravalent distance magic circulants and distance magic Hamming graphs.

  We are looking forward to meeting you at FAMNIT-MP1. 

Our Math Research Seminar will also be broadcasted via Zoom.

Join the Zoom Meeting Here.

 Everyone is welcome and encouraged to attend.

I'll present some joint work with Eda Kaja in which we have constructed a new infinite family of locally transitive graphs. For a given graph in this family, the full automorphism group has two orbits on the vertex set, on one orbit the action is quasiprimitive of Twisted Wreath type and on the other orbit the action is not quasiprimitive. Thus these graphs fall into the class of `star normal quotients'. Previously only one such example was known.

  We are looking forward to meeting you at FAMNIT-MP1. 

This Monday, November 29,  2021, from 10 am to 11 am.

Our Math Research Seminar will also be broadcasted via Zoom.

Join Zoom Meeting Here.

Everyone is welcome and encouraged to attend.

The independence number of a tree decomposition T of a graph is the smallest integer k such that each bag of T induces a subgraph with independence number at most k. If a graph is given together with a tree decomposition with a bounded independence number, then the Maximum Weight Independent Set (MWIS) problem can be solved in polynomial time. Motivated by this observation, we consider six graph containment relations---the subgraph, topological minor, and minor relations, as well as their induced variants---and for each of them characterize the graphs H for which any graph excluding H with respect to the relation admits a tree decomposition with bounded independence number. Furthermore, using a variety of tools including SPQR trees and potential maximal cliques, we show how to obtain such tree decompositions efficiently.

As an immediate consequence, we obtain that the MWIS problem can be solved in polynomial time in an infinite family of graph classes that properly contain the class of chordal graphs. In fact, our approach shows that the Maximum Weight Independent H-Packing problem, a common generalization of the MWIS and the Maximum Weight Induced Matching problems, can be solved in polynomial time in these graph classes.

This is joint work with Martin Milanič and Kenny Štorgel.

We are looking forward to meeting you at FAMNIT-MP1. 

This Monday, November 22,  2021, from 10 am to 11 am.

Our Math Research Seminar will also be broadcasted via Zoom.

Join Zoom Meeting Here.

 Everyone is welcome and encouraged to attend.

There are several possibilities to  generalize the relation of orthogonality from Euclidean to arbitrary normed spaces. Among the better known is Birkhoff-James orthogonality, which is defined, in one of the equivalent ways, as $x \perp y$ if  $y$ lies in the kernel of the supporting functional for $x$. This relation is homogeneous in both factors, but unlike Euclidean space it is not necessarily additive nor symmetric. We assign a (directed) graph to this  relation with  the nonzero vectors as the nodes  and where each pair of  orthogonal vectors forms a directed edge.

With the help of this graph one can show that Birkhoff-James orthogonality alone knows how to calculate the  dimension of  the underlying space, it knows whether the norm is smooth or not and whether it  is strictly convex or not, and actually knows everything about the norm of smooth reflexive spaces  up to (conjugate) linear isometry.

Among possible  applications we mention the study of homomorphisms of the relation (i.e. not necessarily linear mappings that preserve orthogonality).

This is a joint work with  Lj. Arambašić, A. Guterman, R. Rajić, and S. Zhilina
 

  We are looking forward to meeting you at FAMNIT-MP1. 

This Monday, November 8,  2021, from 10 am to 11 am.

Our Math Research Seminar will also be broadcasted via Zoom.

Join Zoom Meeting Here.

Everyone is welcome and encouraged to attend.

A graph is called equimatchable if all of its maximal matchings have the same size. Frendrup et.al. provided a characterization of equimatchable graphs with girth at least 5. In this work, we extend this result by providing a complete structural characterization of equimatchable graphs with  girth at least 4, that is, equimatchable graphs with no triangle, by identifying the equimatchable triangle-free graph families. Our characterization also extends the result given by Akbari et. al.  which proves that the only connected triangle-free equimatchable r-regular graphs are C5, C7 and Kr,r, where r is a positive integer. Given a non-bipartite graph, our characterization implies a linear time recognition algorithm for triangle-free equimatchable graphs.

Join Zoom Meeting Here.

 See you there!

 This Monday, October 4,  2021, from 10 am to 11 am.

 Everyone is welcome and encouraged to attend.

In this talk I shall speak about Painleve equations, special nonlinear differential equations of second order, that appear in many applications. 

I shall explain relation to the recurrence coefficients of certain semiclassical orthogonal polynomials and also show related Hamiltonian systems.

Join Zoom Meeting Here.

 See you there!

 This Monday, October 11,  2021, from 10 am to 11 am.

 Everyone is welcome and encouraged to attend.

We propose a new kind of sliding-block puzzle, called Gourds, where the objective is to rearrange 1 x 2 pieces on a hexagonal grid board of 2n + 1 cells with n pieces, using sliding, turning, and pivoting moves. This puzzle has a single empty cell on a board and forms a natural extension of the 15-puzzle to include rotational moves. We analyze the puzzle and completely characterize the cases when the puzzle can always be solved. We also study the complexity of determining whether a given set of colored pieces can be placed on a colored hexagonal grid board with matching colors. We show this problem is NP-complete for arbitrarily many colors, but solvable in randomized polynomial time if the number of colors is a fixed constant.
 

Join Zoom Meeting Here.

 See you there!

 This Monday, October 18,  2021, from 10 am to 11 am.

 Everyone is welcome and encouraged to attend.

 A set of permutations $\mathcal{F}$ of a finite transitive group $G\leq \sym(\Omega)$ is \emph{intersecting} if any two permutations in $\mathcal{F}$ agree on an element of $\Omega$. The transitive group $G$ is said to have the \emph{Erd\H{o}s-Ko-Rado (EKR) property} if any intersecting set of $G$ has size at most $\frac{|G|}{|\Omega|}$.

    The alternating group $Alt(4)$ acting on the six $2$-subsets of $\{1,2,3,4\}$ is an example of groups without the EKR property. Hence, transitive groups need not have the EKR property.    Given a transitive group $G\leq \sym(\Omega)$, we are interested in finding the size and structure of the largest intersecting sets in $G$. In this talk, we will give an overview of the EKR-theory for transitive groups and present some recent development in this area.

Join Zoom meeting here: 

https://upr-si.zoom.us/j/86104965231?pwd=SFZoMWFpbTN4SmtCMXc1OVVQQmVEQT09

We are looking forward to meeting at the video conference. 

See you there!

Let $\Omega$ be a finite set and $G$ be a permutation group on it.

A subset $A$ of $G$ is \textit{intersecting} if for every $\delta,~\tau \in A$, they agree at some points, i.e. there exists $x \in \Omega$ such that $\delta(x)=\tau(x)$. 

In this talk, I will give an analog of the classical Erd\H{o}s–Ko–Rado theorem for intersecting sets of a group.  I will present a history and overview of some of the results that have been proved on this subject. Finally,  I will discuss some of my results about intersecting sets of the general linear group and its subgroups.

Join Zoom meeting here: 

https://upr-si.zoom.us/j/83882798074?pwd=VTdlLzVmRExBWGdwY1pTZFAvUkZMdz09

Let G be a finite group and let P(G, s) be the probability that an s-tuple of elements in G generate G. Due to Hall, there is a finite Dirichlet series expression for P(G, s), obtained by using the principle of Möbius inversion on partially ordered sets. Brown defined an analogous function P(L, s) for finite lattices, ultimately showing that P(C(G), s+1) = P(G, s), where C(G) is the coset lattice of the group G, that is, P(G, s) only depends on the coset lattice of G.

The re-pairing problem is a recently discovered combinatorial problem concerning Dyck words. We have first identified the re-pairing problem when studying an open question in automata theory, the complexity of translation of one-counter automata (OCA) on finite words into Parikh-equivalent nondeterministic finite automata (NFA). But it appears that the re-pairing problem has natural connections with other combinatorial problems arising in analysis of weak models of computation (e.g., black-and-white 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 depth-first search trees.

 Join Zoom Meeting Here!

Let G denote a distance-biregular 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: 

1. for all i (1 \leq i \leq D-2) 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 i-1 from z is independent of the choice of x,y and z. 

2. for all i (1 \leq i \leq D-1) 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 i-1 from z is independent of the choice of x,y and z. 

Distance-biregular graphs with the previous combinatorial structures are called almost 2-Y-homogeneous and 2-Y-homogeneous, 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 triangle-free 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}{r-1}) \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, non-edge-colored) 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 edge-colored, 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 video-conference.

Join Zoom Meeting HERE!

For more info visit our YouTube Channel.

Motivated by the problems appearing in the theory of experimental designs, Bose and Mesner introduced in 1959 a special class of matrix algebras, known nowadays as Bose-Mesner algebras of symmetric association schemes. In the same year, Shah published the paper where he proposed a more general idea: to replace the standard matrix product with the Jordan product. So, in fact, he introduced the objects called later Jordan schemes by Cameron. While the ideas of Bose and Mesner led to a new direction in algebraic graph theory called later algebraic combinatorics by Bannai and Ito, Shah's idea was not developed at all. Only in 2004 Shah's approach was analyzed by Bailey. She observed that the symmetrization of any association scheme is a Jordan scheme, which led to the following question posed by Cameron: "Are there any others?". In my talk, I'm going to present some constructions of Jordan schemes that provide an affirmative answer to Cameron's question.

This is joint work with M. Klin and Sven Reichard.

We are looking forward to meeting at the video-conference.

Join Zoom Meeting HERE!

For more info visit our YouTube Channel.

A cyclic coloring of a plane graph is a vertex coloring in which all vertices incident with the same face receive distinct colors.
It is conjectured that every plane graph with maximum face size $\Delta^*$ admits a cyclic edge-coloring with at most $\lfloor 3\Delta^*/2 \rfloor$ colors. Since in the case of plane triangulations this coloring corresponds to a proper coloring, the Four Color Theorem implies the conjecture for $\Delta^* = 3$.

As a generalization of cyclic coloring, a $k$-facial coloring was introduced, where vertices at facial distance at most $k$ receive distinct colors. An open conjecture states that every plane graph admits a $k$-facial coloring with $3k + 1$ colors.

Similarly, an $\ell$-facial edge-coloring of a plane graph is a coloring of its edges such that any two edges at distance at most $\ell$ on a boundary walk of any face receive distinct colors.
One can see that this is a more restricted version of the $k$-facial coloring by taking the medial graph $M(G)$ of a plane graph $G$.

However, there exist graphs that require $3\ell + 1$ colors for an $\ell$-facial edge-coloring. Therefore it is also conjectured that $3\ell + 1$ colors suffice for an $\ell$-facial edge-coloring of any plane graph.
While the cases with $\ell = 1$ and $\ell = 2$ are already established, the general case is still wide open.
In our talk, we give a short history of the topic and present a proof of the case $\ell = 3$.\\

This is a joint work with Borut Lu\v{z}ar.

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

This paper discusses the political donations - public procurement interplay. It rests on a unique and comprehensive hand-collected firm-by-tender micro-level dataset that enables the assessment of partisan favouritism in procuring goods, services and work by the Croatian government in the 2012-2018 period. Main results show that (i) political donations pay off and a ten percent increase in political donations leads to an increase in public procurement revenues of 5.7%; (ii) political disloyalty, i.e. switching donations from centre-right to centre-left parties or vice versa, does not reimburse; (iii) big firms in Croatia are big enough to bid lower prices and/or contract better terms, such that they don’t need favouritism in public procurement awards; and (iv) political contributions ex-post election (2016-2018) increase procurement revenues of donating firms by 27%, and firms connected to the losing party exhibit a drop in procurement revenues of more than 12% compared to the ex-ante elections.

 Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For a graph G​​, and two distinct vertices u​​ and v​​ of G​​, let n_G(u,v)​​ be the number of vertices of G​​ that are closer in G​​ to u​​ than to v​​. Miklavi\v{c} and \v{S}parl (arXiv:2011.01635v1) define the distance-unbalancedness {uB}(G)​​ of G​ as the sum of |n_G(u,v)-n_G(v,u)|​ over all unordered pairs of distinct vertices u​​ and v​​ of G​​. For positive integers n​​ up to 15​​, they determine the trees T​​ of fixed order n​ with the smallest and the largest values of { uB}(T)​​, respectively. While the smallest value is achieved by the star K_1,n-1​​ for these n​​, the structure of the trees maximizing the distance-unbalancedness remained unclear. For n​​ up to 15​​ at least, all these trees were subdivided stars. Contributing to problems posed by Miklavi\v{c} and \v{S}parl, we show that stars minimize distance-unbalancedness among all trees of a given order, that

and that

where S(n₁,…,n_k)​​ is the subdivided star such that removing its center vertex leaves paths of orders n₁,…,n_k​​.

Join Zoom Meeting HERE!

 See you there!

 Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.

Computer-aided geometric design (CAGD) deals with the mathematical description, and computational aspects of geometric objects, such as parametric curves and surfaces. It is a field of mathematical nature with relevant use in computer science and engineering. Approximation theory studies the process of approximating general functions by simple functions such as polynomials or splines. Therefore, it plays a central role in the analysis of numerical methods, particularly in approximation of partial differential equations. During the lecture, I will show how my research interests connect the fields of Computer-aided geometric design and Approximation theory. The following two research topics, in which I have been most active in the last decade, will be briefly presented. Parameterization of curves and surfaces are basic concepts in CAGD. In several applications, it is desirable for these curves and surfaces to have some particular properties, such as polynomial arc-length and rational offsets. A special class of curves that satisfies these requirements are Pythagorean-hodograph curves, of which the first part of my talk will be devoted. In the second part, we will get acquainted with a recent method for numerical solution of partial differential equations, i.e., Isogeometric Analysis. The main advantage of this method is in the use of the same standard CAGD spline functions both for describing the geometry and for the numerical simulation of partial differential equations. The increased smoothness of the spline functions compared to traditional finite elements allows for improved stability and convergence properties.

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

 For more info visit our YouTube Channel.

We often observe that people help strangers in real life. Such altruistic behaviour is puzzling for economics and biology because it promotes the welfare of another person at a cost to oneself. It is also difficult to explain it by long-term strategic motivations when the recipient is a stranger who may not be able to return a favour. Real-life evidence does not offer many opportunities to learn about the motivations behind individual altruism, unfortunately.

 In this project, we instead investigate reciprocal altruism in a laboratory experiment with people playing a long-term economic game of indirect reciprocity. This experiment provides sufficiently detailed data about motivations for altruism to facilitate the classification of almost 90% of participants into several theoretically feasible strategies. For this, we apply a recently developed statistical method to our indirect reciprocity experiment. We compare the resulting classification to the classifications of three other existing methods in the literature and demonstrate that it is the closest to a consensus measure. We then show how the other three existing methods ignore a learning strategy that is used by almost half of the subjects in one of our experimental treatments. Finally, we compare the strategy classification to people's self-reports and show that these are a very unreliable source of data about individual motivations for altruism.

Let Γ denote an undirected, connected, regular graph with vertex set X, adjacency matrix A, and d+1 distinct eigenvalues. Let {\cal A}={\cal A}(Γ) denote the subalgebra of Mat_X(C) generated by A. We refer to {\cal A} as the {\em adjacency algebra} of Γ. In this talk, we investigate the algebraic and combinatorial structure of Γ for which the adjacency algebra {\cal A} is closed under Hadamard multiplication. In particular, under this simple assumption, we show the following: (i) {\cal A} has a standard basis {I,F_1,…,F_d}; (ii) for every vertex there exists identical distance-faithful intersection diagram of Γ with d+1 cells; (iii) the graph Γ is quotient-polynomial; and (iv) if we pick F∈{I,F_1,…,F_d} then F has d+1 distinct eigenvalues if and only if span{I,F_1,…,F_d}=span{I,F,…,F^d}. We describe the combinatorial structure of quotient-polynomial graphs with diameter 2 and 4 distinct eigenvalues.

This is joint work with Miquel À. Fiol.

This talk is based on one part of the preprint available at https://arxiv.org/abs/2009.05343

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.

There are two standard ways to shuffle a deck of cards, the in and out shuffles. For the in shuffle, divide the deck into two piles, hold one pile in each hand and then perfectly interlace the piles, with the top card from the left hand pile being on top of the resulting stack of cards. For the out shuffle, the top card from the right hand pile ends up on top of the resulting stack.

Standard card tricks are based on knowing what permutations of the deck of cards may be achieved just by performing the in and out shuffles. Mathematicians answer this question by solving the problem of what permutation group is generated by these two shuffles. Diaconis, Graham and Kantor were the first to solve this problem in full generality - for decks of size 2*n. The answer is usually “as big as possible”, but with some rather beautiful and surprising exceptions. In this talk, I’ll explain how the number of permutations is limited, and give some hints about how to obtain different permutations of the deck. I’ll also present a more general question about a “many handed dealer” who shuffles k*n cards divided into k piles.

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.

I will present a deterministic model for disease transmission dynamics including diagnosis of symptomatic individuals and contact tracing. The model is structured by time since infection and formulated in terms of the individual disease rates and the parameters characterising diagnosis and contact tracing processes. By incorporating a mechanistic formulation of the processes at the individual level, we obtain an integral equation (delayed in calendar time and advanced in the time since infection) for the probability that an infected individual is detected and isolated at any point in time. This is then coupled with a renewal equation for the total incidence to form a closed system describing the transmission dynamics involving contact tracing. After presenting the derivation of the model, I will conclude with some applications of public health relevance, especially in the context of the ongoing COVID-19 pandemic.

Joint work with Lorenzo Pellis (University of Manchester), Nicholas H Ogden (PHAC, Public Health Agency of Canada) and Jianhong Wu (York University).

Reference: Scarabel F, Pellis L, Ogden NH, Wu J. A renewal equation model to assess roles and limitations of contact tracing for disease outbreak control, available on medRxiv: https://doi.org/10.1101/2020.12.27.20232934

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.

An undirected graph G d-degenerate if every subgraph of G has a vertex of degree at most d, and the degeneracy is the minimum d such that G is d-degenerate. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least d+1. The proof of Erdös and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least d+1. But can we decide in polynomial time whether a graph contains a cycle of length at least d+2? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least d+2 is NP-complete.  Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected.  In this case we prove that    deciding whether G contains a cycle of length at least d+k can be done in time 2^{O(k)}|V(G)|^{O(1)}.  Further, we briefly consider similar problem arising from the classical result of Dirac from 1952 that every 2-connected n-vertex graph has a cycle with at least min{2\delta(G),n} vertices. 

The talk is based on the joint work with Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi, Danil Sagunov, and Kirill Simonov.

We are looking forward to meeting at the video-conference. Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.

It is known that a Cayley digraph $\Cay(A,S)$ of an abelian group $A$ is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup $B\le A$ such that $S\setminus B$ is a union of cosets of $B$ in $A$. We generalize this result to Cayley digraphs $\Cay(G,S)$ to nonabelian groups $G$ by showing that such a digraph is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup $H\le G$ such that $S\setminus H$ is a union of double cosets of $H$ in $G$. This result is proven in the more general situation of a double coset digraph (also known as a Sabidussi coset digraph.) We then give applications of this result which include showing the problem of determining automorphism groups of vertex-transitive digraphs is equivalent to the problem of determining automorphism groups of Cayley digraphs, and extending the definition of generalized wreath product digraphs to double coset digraphs of all groups $G$.

Join Zoom Meeting HERE!

Everyone is welcome and encouraged to attend.

For more info visit our YouTube Channel.