Source author record

Ademir Hujdurović

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.GR Computational Complexity Data Structures and Algorithms Populations and Evolution

Catalog footprint

Research overview

11works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Intersection density of transitive groups with cyclic point stabilizers

For a permutation group $G$ acting on a set $V$ , a subset $\mathcal{F}$ of $G$ is said to be an intersecting set if for every pair of elements $g,h\in \mathcal{F}$ there exists $v \in V$ such that $g(v) = h(v)$ . The intersection density $ρ(G)$ of a transitive permutation group $G$ is the maximum value of the quotient $|\mathcal{F}|/|G_v|$ where $G_v$ is a stabilizer of a point $v\in V$ and $\mathcal{F}$ runs over all intersecting sets in $G$ . If $G_v$ is a largest intersecting set in $G$ then $G$ is said to have the Erdős-Ko-Rado (EKR)-property. This paper is devoted to the study of transitive permutation groups, with point stabilizers of prime order with a special emphasis given to orders 2 and 3, which do not have the EKR-property. Among other, constructions of infinite family of transitive permutation groups having point stabilizer of order $3$ with intersection density $4/3$ and of infinite families of transitive permutation groups having point stabilizer of order $3$ with arbitrarily large intersection density are given.

preprint2021arXiv

Intersection density of transitive groups of certain degrees

Two elements $g$ and $h$ of a permutation group $G$ acting on a set $V$ are said to be intersecting if $g(v) = h(v)$ for some $v \in V$ . More generally, a subset ${\cal F}$ of $G$ is an intersecting set if every pair of elements of ${\cal F}$ is intersecting. The intersection density $ρ(G)$ of a transitive permutation group $G$ is the maximum value of the quotient $|{\cal F}|/|G_v|$ where ${\cal F}$ runs over all intersecting sets in $G$ and $G_v$ is a stabilizer of $v\in V$ . In this paper the intersection density of transitive groups of degree twice a prime is determined, and proved to be either $1$ or $2$ . In addition, it is proved that the intersection density of transitive groups of prime power degree is $1$ .

preprint2021arXiv

On automorphisms of the double cover of a circulant graph

A graph $X$ is said to be "unstable" if the direct product $X \times K_2$ (also called the canonical double cover of $X$ ) has automorphisms that do not come from automorphisms of its factors $X$ and $K_2$ . It is "nontrivially unstable" if it is unstable, connected, and nonbipartite, and no two distinct vertices of X have exactly the same neighbors. We find three new conditions that each imply a circulant graph is unstable. (These yield infinite families of nontrivially unstable circulant graphs that were not previously known.) We also find all of the nontrivially unstable circulant graphs of order $2p$ , where $p$ is any prime number. Our results imply that there does not exist a nontrivially unstable circulant graph of order $n$ if and only if either $n$ is odd, or $n < 8$ , or $n = 2p$ , for some prime number $p$ that is congruent to $3$ modulo $4$ .

preprint2020arXiv

Canonical double covers of circulants

The canonical double cover $B(X)$ of a graph $X$ is the direct product of $X$ and $K_2$ . If $Aut(B(X)) \cong Aut(X) \times \mathbb{Z}_2$ then $X$ is called stable; otherwise $X$ is called unstable. An unstable graph is nontrivially unstable if it is connected, non-bipartite and distinct vertices have different neighborhoods. Circulant is a Cayley graph on a cyclic group. Qin et al. conjectured in [J. Combin. Theory Ser. B 136 (2019), 154-169] that there are no nontrivialy unstable circulants of odd order. In this paper we prove this conjecture.

preprint2020arXiv

Classification of vertex-transitive digraphs via automorphism group

In the mid-1990s, two groups of authors independently obtained classifications of vertex-transitive graphs whose order is a product of two distinct primes. In the intervening years it has become clear that there is additional information concerning these graphs that would be useful, as well as making explicit the extensions of these results to digraphs. Additionally, there are several small errors in some of the papers that were involved in this classification. The purpose of this paper is to fill in the missing information as well as correct all known errors.

preprint2020arXiv

Three local actions in $6$ -valent arc-transitive graphs

It is known that there are precisely three transitive permutation groups of degree $6$ that admit an invariant partition with three parts of size $2$ such that the kernel of the action on the parts has order $4$ ; these groups are called $A_4(6)$ , $S_4(6d)$ and $S_4(6c)$ . For each $L\in \{A_4(6), S_4(6d), S_4(6c)\}$ , we construct an infinite family of finite connected $6$ -valent graphs $\{Γ_n\}_{n\in \mathbb{N}}$ and arc-transitive groups $G_n \le \rm{Aut}(Γ_n)$ such that the permutation group induced by the action of the vertex-stabiliser $(G_n)_v$ on the neighbourhood of a vertex $v$ is permutation isomorphic to $L$ , and such that $|(G_n)_v|$ is exponential in $|\rm{V}(Γ_n)|$ . These three groups were the only transitive permutation groups of degree at most $7$ for which the existence of such a family was undecided. In the process, we construct an infinite family of cubic $2$ -arc-transitive graphs such that the dimension of the $1$ -eigenspace over the field of order $2$ of the adjacency matrix of the graph grows linearly with the order of the graph.

preprint2016arXiv

Complexity and algorithms for finding a perfect phylogeny from mixed tumor samples

Recently, Hajirasouliha and Raphael (WABI 2014) proposed a model for deconvoluting mixed tumor samples measured from a collection of high-throughput sequencing reads. This is related to understanding tumor evolution and critical cancer mutations. In short, their formulation asks to split each row of a binary matrix so that the resulting matrix corresponds to a perfect phylogeny and has the minimum number of rows among all matrices with this property. In this paper we disprove several claims about this problem, including an NP-hardness proof of it. However, we show that the problem is indeed NP-hard, by providing a different proof. We also prove NP-completeness of a variant of this problem proposed in the same paper. On the positive side, we propose an efficient (though not necessarily optimal) heuristic algorithm based on coloring co-comparability graphs, and a polynomial time algorithm for solving the problem optimally on matrix instances in which no column is contained in both columns of a pair of conflicting columns. Implementations of these algorithms are freely available at https://github.com/alexandrutomescu/MixedPerfectPhylogeny

preprint2015arXiv

On automorphisms and structural properties of generalized Cayley graphs

In this paper, generalized Cayley graphs are studied. It is proved that every generalized Cayley graph of order 2p is a Cayley graph, where p is a prime. Special attention is given to generalized Cayley graphs on Abelian groups. It is proved that every generalized Cayley graph on an Abelian group with respect to an automorphism which acts as inversion is a Cayley graph if and only if the group is elementary Abelian 2-group, or its Sylow 2-subgroup is cyclic. Necessary and sufficient conditions for a generalized Cayley graph to be unworthy are given.

preprint2015arXiv

On Color Preserving Automorphisms of Cayley Graphs of Odd Square-free Order

An automorphism $α$ of a Cayley graph $Cay(G,S)$ of a group $G$ with connection set $S$ is color-preserving if $α(g,gs) = (h,hs)$ or $(h,hs^{-1})$ for every edge $(g,gs)\in E(Cay(G,S))$ . If every color-preserving automorphism of $Cay(G,S)$ is also affine, then $Cay(G,S)$ is a CCA (Cayley color automorphism) graph. If every Cayley graph $Cay(G,S)$ is a CCA graph, then $G$ is a CCA group. Hujdurović, Kutnar, D.W. Morris, and J. Morris have shown that every non-CCA group $G$ contains a section isomorphic to the nonabelian group $F_{21}$ of order $21$ . We first show that there is a unique non-CCA Cayley graph $Γ$ of $F_{21}$ . We then show that if $Cay(G,S)$ is a non-CCA graph of a group $G$ of odd square-free order, then $G = H\times F_{21}$ for some CCA group $H$ , and $Cay(G,S) = Cay(G,T)\BoxΓ$ .

preprint2015arXiv

On colour-preserving automorphisms of Cayley graphs

We study the automorphisms of a Cayley graph that preserve its natural edge-colouring. More precisely, we are interested in groups G, such that every such automorphism of every connected Cayley graph on G has a very simple form: the composition of a left-translation and a group automorphism. We find classes of groups that have the property, and we determine the orders of all groups that do not have the property. We also have analogous results for automorphisms that permute the colours, rather than preserving them.

preprint2014arXiv

Vertex-transitive CIS graphs

A CIS graph is a graph in which every maximal stable set and every maximal clique intersect. A graph is well-covered if all its maximal stable sets are of the same size, co-well-covered if its complement is well-covered, and vertex-transitive if, for every pair of vertices, there exists an automorphism of the graph mapping one to the other. We show that a vertex-transitive graph is CIS if and only if it is well-covered, co-well-covered, and the product of its clique and stability numbers equals its order. A graph is irreducible if no two distinct vertices have the same neighborhood. We classify irreducible well-covered CIS graphs with clique number at most 3 and vertex-transitive CIS graphs of valency at most 7, which include an infinite family. We also exhibit an infinite family of vertex-transitive CIS graphs which are not Cayley.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ademir Hujdurović

Research overview

Is this your work?

11 publications

Intersection density of transitive groups with cyclic point stabilizers

Intersection density of transitive groups of certain degrees

On automorphisms of the double cover of a circulant graph

Canonical double covers of circulants

Classification of vertex-transitive digraphs via automorphism group

Three local actions in $6$ -valent arc-transitive graphs

Complexity and algorithms for finding a perfect phylogeny from mixed tumor samples

On automorphisms and structural properties of generalized Cayley graphs

On Color Preserving Automorphisms of Cayley Graphs of Odd Square-free Order

On colour-preserving automorphisms of Cayley graphs

Vertex-transitive CIS graphs

See the researcher in context

Building this map preview

Ademir Hujdurović

Research overview

Is this your work?

11 publications

Intersection density of transitive groups with cyclic point stabilizers

Intersection density of transitive groups of certain degrees

On automorphisms of the double cover of a circulant graph

Canonical double covers of circulants

Classification of vertex-transitive digraphs via automorphism group

Three local actions in 666-valent arc-transitive graphs

Complexity and algorithms for finding a perfect phylogeny from mixed tumor samples

On automorphisms and structural properties of generalized Cayley graphs

On Color Preserving Automorphisms of Cayley Graphs of Odd Square-free Order

On colour-preserving automorphisms of Cayley graphs

Vertex-transitive CIS graphs

See the researcher in context

Building this map preview

Three local actions in $6$ -valent arc-transitive graphs