bluuebunny/crossref_metadata_2025 huggingface dataset:
Assessing Antimicrobial Resistance, Utilization, and Stewardship in Yemen: An Exploratory Mixed-Methods Study
Authors: Orubu Ebiowei S. F. , Al-Dheeb Najwa , Ching Carly , Bu Jawdeh Sima , Anderson Jessica , Sheikh Rashad , Hariri Fadhel , Basaleem Huda , Zaman Muhammad H.
Published: August 2021

Antimicrobial resistance (AMR), largely driven by irrational use of antimicrobials, is a global, multifaceted problem calling for a complete understanding of all contributory factors for effective containment. In conflict settings, war-wounds and malnutrition can combine with existing social determinants to increase demand for antibiotics, compounding irrational use. In this study, we focus on Yemen, a low-income country with active conflict for the last 5 years, and analyze the current status of awareness and stewardship efforts regarding AMR. We performed a survey of prescribers/physicians and pharmacists to describe perceptions of AMR prevalence, antibiotic use practices, and stewardship in Yemen, supported by a nonsystematic scoping literature review and a key informant interview. Participants (96%, N = 54) reported a perceived high AMR prevalence rate. Prescribers (74%, 20/27) reported pressure to prescribe broad-spectrum antibiotics. In the majority of cases (81%, 22/27), antimicrobial sensitivity tests (AST) were not performed to inform antibiotic choice. The main barrier to AST was cost. Most pharmacists (67%, 18/27) sold antibiotics without prescriptions. Amoxicillin (including amoxicillin-clavulanate) was the most-commonly prescribed (63%, 17/27) or dispensed (81%, 22/27) antibiotic. AST was rated the least important solution to AMR in Yemen. While there was awareness of a high AMR rate, stewardship is poor in Yemen. We note that barriers to the use of AST could be addressed through the deployment of reliable, affordable, quality rapid diagnostics, and AST kits. Compulsory continuing education emphasizing the use of AST to guide prescribing and patients’ awareness programs could help avoid irrational use.
Prevalence of parasitic infections on cultured Nile tilapia, Oreochromis niloticus (Linnaeus, 1758) In Bong County, Liberia
Authors: Addo S. , Mullah S. , Ofori-Danson P. K. , Amponsah S. K. K. , Nyarko J. O.
Published: August 2021

This study investigated the prevalence rate, relative abundance and mean intensity of par­asites infecting cultured Nile tilapia Oreochromis niloticus L. in three fish farms, Gbarnga, Warta and CARI in Bong County, Liberia. Organs from thirty fish samples were exam­ined from September 2016 to February 2017, along with water quality parameters. Results showed the occurrence of seven parasites including protozoans, monogeneans, digeneans, cestodes, hirudineans, nematodes and crustaceans which were organ specific in terms of infection. The prevalence of the parasites varied seasonally, with the highest numbers oc­curring in November-January. The low prevalence rate, relative abundance and mean in­tensity of the parasites showed no threat to fish farmers in Liberia. All the water quality parameters were at desirable levels for the culture of the fish except nitrite, which was beyond the threshold for sustainable fish culture. It is therefore concluded that although parasitic infections in the three farms in the Bong County were low, best farm management practices are essential.
Influence of salicylic acid and potassium nitrate on plant height and flowering time of groundnut (Arachis hypogaea L.) under varying salinity and drought-induced stresses
Authors: Nkrumah P. , Amadu A. M. , Ayeh K. O.
Published: August 2021

This study was conducted to examine the effects of Salicylic acid (SA) and Potassium nitrate (KNO3) on plant height and flowering time of groundnut (Arachis hypogaea L.) under induced stresses of salinity, drought and combined salinity and drought. Three watering regimes namely; normal, moderate and severe were used. For salinity stress, 50 mM NaCl, 100 mM NaCl, 150 mM NaCl and combination of water and salinity regimes were used. 50 μm KNO3 and 50 μm SA were separately applied to plants under water, salinity and combined water and salinity stresses. The mean plant height at 100 mM salt concentration were 42.29 cm for KNO3, 42.27 cm for SA, compared with 40.98 cm for control (F = 2.73; P ≤ 0.008). In combined severe watering and 150 mM NaCl treatment, flowering time was 57 DAP (days after planting) compared to 34 DAP in control plants. When KNO3 and SA were applied to severe watering and 150 mM NaCl combined stress induced plants, flowering time was 51 DAP and 53 DAP for KNO3 and SA treated plants respectively. In conclusion, the exogenous application of plant growth regulators such as SA and KNO3 reduce impact of water stress on groundnut and effectively improve yield.
Pristojnosti in naloge slovenskih občin (s pregledom splošnih in posamičnih aktov ter aktov poslovanja občine): petnajsta spremenjena in dopolnjena izdaja
Authors:   Inštitut za lokalno samoupravo Maribor, Brezovnik Boštjan
Published: August 2021

Inštitut za lokalno samoupravo, javne službe in javno-zasebno partnerstvo Maribor pripravlja in usklajuje katalog 'Pristojnosti slovenskih občin' v pisni in elektronski obliki (dostopen na www.lex-localis.info), ki je že več kot desetletje pomemben strokovni priročnik za delovanje občin. V katalogu je podan pregled pristojnosti in nalog občine po posameznih predpisih Državnega zbora, Vlade Republike Slovenije in ministrstev. Pristojnosti organov občine so podane posebej za občinski svet, župana, občinsko upravo in druge organe oziroma telesa v občini. Vsi predpisi, ki določajo naloge in pristojnosti občin so razdeljeni v 10 osnovnih poglavij in v okviru teh na podpoglavja, kjer so razvrščeni posamezni predpisi. Pristojnosti so podane v kratkih povzetkih pravnih osnov oziroma členov, ki jih določajo. V katalogu 'Pristojnosti slovenskih občin' so objavljene zbirke obsežnih strokovnih vsebin, podatkov, osnutkov aktov, primerov iz prakse in pripomočkov z vseh področij pristojnosti slovenskih občin.
Determinants of International Tourists’ Destination Loyalty: Empirical Evidence from Serengeti National Park in Tanzania
Authors: Matolo Richard , Salia Paul , Ndibalema Vedasto
Published: August 2021

This study was conducted to assess the determinants of tourists’ loyalty to Serengeti National Park (SENAPA) in Tanzania. The study involved 1,148 respondents who were international tourists visiting the park from March to December 2018. Data were collected using a structured survey questionnaire. Structural Equation Modelling (SEM) technique was used in the analysis. Findings revealed that service quality was a positive predictor of tourists’ loyalty. Accordingly, destination image and perceived value had positive effects on tourists destination loyalty. Also, satisfaction was found to have positive effect on destination loyalty. Furthermore, the findings revealed that satisfaction had a partial mediation effect on the relationship between service quality, destination image and perceived value on the one hand and destination loyalty on the other. It was concluded that provision of high-quality services increased tourists’ loyalty to the park. Similarly, tourists’ satisfaction and realization of value during their trips increased loyalty. The study calls for SENAPA management to strive to maintain high quality of services provided to tourists by introducing service provision charter that would guide the operations of different stakeholders inside the park. Also, the park’s management should make efforts that would enhance perceived value among the tourists by reviewing costs of items charged on tourists like park entry fees in view of making them competitive compared to similar parks found in Africa.
Bazı Tane Sorgum ve Sorgum X Sudanotu Melezi Çeşitlerinde Ekim Zamanının Verim ve Verim Unsurlarına Etkisi Üzerine Bir Araştırma
Authors: Kemal YILDIRIM  , Gülşah BENGİSU
Published: August 2021

Bu araştırma bazı tane sorgum ve sorgum sudanotu melezi çeşitlerinde ekim zamanının verim ve verim unsurlarına etkisi üzerine Toprak Mahsulleri Ofisi Viranşehir Ajans Müdürlüğü tesisleri uygulama arazisinde yürütülmüştür. Deneme bölünmüş parseller deneme desenine göre 3 tekerrürlü olarak oluşturulmuştur. Araştırmada ana parselleri çeşitler,  Kws,  Fito,  Hay day ve Akdarı alt parselleri ise ekim zamanları 25 Haziran, 5 Temmuz ve 15 Temmuz olarak oluşturulmuştur. 3 farklı zamanda ekimi yapılan sorgumun bölünmüş parseller deneme desenine göre analizler yapılmıştır. Analizlerle: % 50 çiçeklenme gün sayısı, olgunlaşma gün sayısı, bitki boyu, yaprak sayısı, sap kalınlığı, salkım uzunluğu, salkım ağırlığı, salkım başına tane verimi, salkım başına tane sayısı, salkımda tane oranı, tane verimi, 1000 tane ağırlığı, hektolitre ağırlığı ve ham protein oranı sonuçları incelenmiştir. Bu araştırma sonucunda ele alınan özellikler irdelendiğinde Şanlıurfa ili Viranşehir ilçesi koşullarında sorgum bitkisinin tane verimi bakımından Akdarı ve Hay day çeşitlerinin ilk ekim zamanı, yeşil ot bakımından Fito ve Kws çeşitlerinin ilk ekim zamanı önerilmektedir.
Canonical forms for free κ-semigroups
Authors: Costa José Carlos
Published: August 2021

Automata, Logic and Semantics

The implicit signature κ consists of the multiplication and the (ω-1)-power. We describe a procedure to transform each κ-term over a finite alphabet A into a certain canonical form and show that different canonical forms have different interpretations over some finite semigroup. The procedure of construction of the canonical forms, which is inspired in McCammond\textquoterights normal form algorithm for ω-terms interpreted over the pseudovariety A of all finite aperiodic semigroups, consists in applying elementary changes determined by an elementary set Σ of pseudoidentities. As an application, we deduce that the variety of κ-semigroups generated by the pseudovariety S of all finite semigroups is defined by the set Σ and that the free κ-semigroup generated by the alphabet A in that variety has decidable word problem. Furthermore, we show that each ω-term has a unique ω-term in canonical form with the same value over A. In particular, the canonical forms provide new, simpler, representatives for ω-terms interpreted over that pseudovariety.
An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n+1) - p(n) ≤ 2
Authors: Leroy Julien
Published: August 2021

Automata, Logic and Semantics

An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n + 1) − p(n) ≤ 2 S. Ferenczi proved that any minimal subshift with first difference of complexity bounded by 2 is S-adic with Card(S) ≤ 3 27. In this paper, we improve this result by giving an S-adic characterization of these subshifts with a set S of 5 morphisms, solving by this way the S-adic conjecture for this particular case.
A combinatorial non-commutative Hopf algebra of graphs
Authors: Tanasa Adrian , Duchamp Gerard , Foissy Loïc , Hoang-Nghia Nguyen , Manchon Dominique
Published: August 2021

Combinatorics

A non-commutative, planar, Hopf algebra of planar rooted trees was defined independently by one of the authors in Foissy (2002) and by R. Holtkamp in Holtkamp (2003). In this paper we propose such a non-commutative Hopf algebra for graphs. In order to define a non-commutative product we use a quantum field theoretical (QFT) idea, namely the one of introducing discrete scales on each edge of the graph (which, within the QFT framework, corresponds to energy scales of the associated propagators). Finally, we analyze the associated quadri-coalgebra and codendrifrom structures.
A Parameterized Measure-and-ConquerAnalysis for Finding a k-Leaf Spanning Treein an Undirected Graph
Authors: Binkele-Raible Daniel , Fernau Henning
Published: August 2021

Discrete Algorithms

The problem of finding a spanning tree in an undirected graph with a maximum number of leaves is known to be NP-hard. We present an algorithm which finds a spanning tree with at least k leaves in time O*(3.4575k) which improves the currently best algorithm. The estimation of the running time is done by using a non-standard measure. The present paper is one of the still few examples that employ the Measure & Conquer paradigm of algorithm analysis in the area of Parameterized Algorithmics.
The generalized 3-connectivity of Lexicographic product graphs
Authors: Li Xueliang , Mao Yaping
Published: August 2021

Graph Theory

The generalized k-connectivity κk(G) of a graph G, first introduced by Hager, is a natural generalization of the concept of (vertex-)connectivity. Denote by G^H and G&Box;H the lexicographic product and Cartesian product of two graphs G and H, respectively. In this paper, we prove that for any two connected graphs G and H, κ3(G^H)≥ κ3(G)|V(H)|. We also give upper bounds for κ3(G&Box; H) and κ3(G^H). Moreover, all the bounds are sharp.
Partitioning the vertex set of $G$ to make $G\,\Box\, H$ an efficient open domination graph
Authors: Šumenjak Tadeja Kraner , Peterin Iztok , Rall Douglas F. , Tepeh Aleksandra
Published: August 2021

A graph is an efficient open domination graph if there exists a subset of
vertices whose open neighborhoods partition its vertex set. We characterize
those graphs $G$ for which the Cartesian product $G \Box H$ is an efficient
open domination graph when $H$ is a complete graph of order at least 3 or a
complete bipartite graph. The characterization is based on the existence of a
certain type of weak partition of $V(G)$. For the class of trees when $H$ is
complete of order at least 3, the characterization is constructive. In
addition, a special type of efficient open domination graph is characterized
among Cartesian products $G \Box H$ when $H$ is a 5-cycle or a 4-cycle.
Asymptotic Density of Zimin Words
Authors: Cooper Joshua , Rorabaugh Danny
Published: August 2021

Word $W$ is an instance of word $V$ provided there is a homomorphism $\phi$
mapping letters to nonempty words so that $\phi(V) = W$. For example, taking
$\phi$ such that $\phi(c)=fr$, $\phi(o)=e$ and $\phi(l)=zer$, we see that
"freezer" is an instance of "cool".
Let $\mathbb{I}_n(V,[q])$ be the probability that a random length $n$ word on
the alphabet $[q] = \{1,2,\cdots q\}$ is an instance of $V$. Having previously
shown that $\lim_{n \rightarrow \infty} \mathbb{I}_n(V,[q])$ exists, we now
calculate this limit for two Zimin words, $Z_2 = aba$ and $Z_3 = abacaba$.
The permutation class Av(4213,2143)
Authors: Bevan David
Published: August 2021

We determine the structure of permutations avoiding the patterns 4213 and
2143. Each such permutation consists of the skew sum of a sequence of plane
trees, together with an increasing sequence of points above and an increasing
sequence of points to its left. We use this characterisation to establish the
generating function enumerating these permutations. We also investigate the
properties of a typical large permutation in the class and prove that if a
large permutation that avoids 4213 and 2143 is chosen uniformly at random, then
it is more likely than not to avoid 2413 as well.
A Bijection on Classes Enumerated by the Schröder Numbers
Authors: Schroeder Michael W. , Smith Rebecca
Published: August 2021

We consider a sorting machine consisting of two stacks in series where the
first stack has the added restriction that entries in the stack must be in
decreasing order from top to bottom. The class of permutations sortable by this
machine are known to be enumerated by the Schröder numbers. In this paper, we
give a bijection between these sortable permutations of length $n$ and
Schröder paths -- the lattice paths from $(0,0)$ to $(n-1,n-1)$ composed of
East steps $(1,0)$, North steps $(0,1)$, and Diagonal steps $(1,1)$ that travel
weakly below the line $y=x$.
Most Complex Regular Ideal Languages
Authors: Brzozowski Janusz , Davies Sylvie , Liu Bo Yang Victor
Published: August 2021

A right ideal (left ideal, two-sided ideal) is a non-empty language $L$ over
an alphabet $\Sigma$ such that $L=L\Sigma^*$ ($L=\Sigma^*L$,
$L=\Sigma^*L\Sigma^*$). Let $k=3$ for right ideals, 4 for left ideals and 5 for
two-sided ideals. We show that there exist sequences ($L_n \mid n \ge k $) of
right, left, and two-sided regular ideals, where $L_n$ has quotient complexity
(state complexity) $n$, such that $L_n$ is most complex in its class under the
following measures of complexity: the size of the syntactic semigroup, the
quotient complexities of the left quotients of $L_n$, the number of atoms
(intersections of complemented and uncomplemented left quotients), the quotient
complexities of the atoms, and the quotient complexities of reversal, star,
product (concatenation), and all binary boolean operations. In that sense,
these ideals are "most complex" languages in their classes, or "universal
witnesses" to the complexity of the various operations.
Right-jumps and pattern avoiding permutations
Authors: Banderier Cyril , Baril Jean-Luc , Santos Céline Moreira Dos
Published: August 2021

We study the iteration of the process "a particle jumps to the right" in
permutations. We prove that the set of permutations obtained in this model
after a given number of iterations from the identity is a class of pattern
avoiding permutations. We characterize the elements of the basis of this class
and we enumerate these "forbidden minimal patterns" by giving their bivariate
exponential generating function: we achieve this via a catalytic variable, the
number of left-to-right maxima. We show that this generating function is a
D-finite function satisfying a nice differential equation of order~2. We give
some congruence properties for the coefficients of this generating function,
and we show that their asymptotics involves a rather unusual algebraic exponent
(the golden ratio $(1+\sqrt 5)/2$) and some unusual closed-form constants. We
end by proving a limit law: a forbidden pattern of length $n$ has typically
$(\ln n) /\sqrt{5}$ left-to-right maxima, with Gaussian fluctuations.
Automata in SageMath---Combinatorics meet Theoretical Computer Science
Authors: Heuberger Clemens , Krenn Daniel , Kropf Sara
Published: August 2021

The new finite state machine package in the mathematics software system
SageMath is presented and illustrated by many examples. Several combinatorial
problems, in particular digit problems, are introduced, modeled by automata and
transducers and solved using SageMath. In particular, we compute the asymptotic
Hamming weight of a non-adjacent-form-like digit expansion, which was not known
before.
Ramsey-type theorems for lines in 3-space
Authors: Cardinal Jean , Payne Michael S. , Solomon Noam
Published: August 2021

We prove geometric Ramsey-type statements on collections of lines in 3-space.
These statements give guarantees on the size of a clique or an independent set
in (hyper)graphs induced by incidence relations between lines, points, and
reguli in 3-space. Among other things, we prove that: (1) The intersection
graph of n lines in R^3 has a clique or independent set of size Omega(n^{1/3}).
(2) Every set of n lines in R^3 has a subset of n^{1/2} lines that are all
stabbed by one line, or a subset of Omega((n/log n)^{1/5}) such that no
6-subset is stabbed by one line. (3) Every set of n lines in general position
in R^3 has a subset of Omega(n^{2/3}) lines that all lie on a regulus, or a
subset of Omega(n^{1/3}) lines such that no 4-subset is contained in a regulus.
The proofs of these statements all follow from geometric incidence bounds --
such as the Guth-Katz bound on point-line incidences in R^3 -- combined with
Tur\'an-type results on independent sets in sparse graphs and hypergraphs.
Although similar Ramsey-type statements can be proved using existing generic
algebraic frameworks, the lower bounds we get are much larger than what can be
obtained with these methods. The proofs directly yield polynomial-time
algorithms for finding subsets of the claimed size.
Stokes posets and serpent nests
Authors: Chapoton Frédéric
Published: August 2021

30 pages, 12 figures

We study two different objects attached to an arbitrary quadrangulation of a regular polygon. The first one is a poset, closely related to the Stokes polytopes introduced by Baryshnikov. The second one is a set of some paths configurations inside the quadrangulation, satisfying some specific constraints. These objects provide a generalisation of the existing combinatorics of cluster algebras and nonnesting partitions of type A.

On étudie deux objets attachés à une quadrangulation quelconque d'un polygone régulier. Le premier objet est un ensemble partiellement ordonné, fortement lié aux polytopes de Stokes introduits par Barysknikov. Le second est un ensemble de configurations de chemins dans la quadrangulation. Ces deux objets généralisent respectivement les aspects combinatoires des algèbres amassées et des partitions non-emboitées de type A.
Enumeration of Corners in Tree-like Tableaux
Authors: Gao Alice L. L. , Gao Emily X. L. , Laborde-Zubieta Patxi , Sun Brian Y.
Published: August 2021

In this paper, we confirm conjectures of Laborde-Zubieta on the enumeration
of corners in tree-like tableaux and in symmetric tree-like tableaux. In the
process, we also enumerate corners in (type $B$) permutation tableaux and
(symmetric) alternative tableaux. The proof is based on Corteel and Nadeau's
bijection between permutation tableaux and permutations. It allows us to
interpret the number of corners as a statistic over permutations that is easier
to count. The type $B$ case uses the bijection of Corteel and Kim between type
$B$ permutation tableaux and signed permutations. Moreover, we give a bijection
between corners and runs of size 1 in permutations, which gives an alternative
proof of the enumeration of corners. Finally, we introduce conjectural
polynomial analogues of these enumerations, and explain the implications on the
PASEP.
Coloring and Guarding Arrangements
Authors: Bose Prosenjit , Cardinal Jean , Collette Sébastien , Hurtado Ferran , Korman Matias , Langerman Stefan , Taslakian Perouz
Published: August 2021

Combinatorics

Given an arrangement of lines in the plane, what is the minimum number c of colors required to color the lines so that no cell of the arrangement is monochromatic? In this paper we give bounds on the number c both for the above question, as well as some of its variations. We redefine these problems as geometric hypergraph coloring problems. If we define $\Hlinecell$ as the hypergraph where vertices are lines and edges represent cells of the arrangement, the answer to the above question is equal to the chromatic number of this hypergraph. We prove that this chromatic number is between Ω(logn/loglogn). and O(n√). Similarly, we give bounds on the minimum size of a subset S of the intersections of the lines in A such that every cell is bounded by at least one of the vertices in S. This may be seen as a problem on guarding cells with vertices when the lines act as obstacles. The problem can also be defined as the minimum vertex cover problem in the hypergraph $\Hvertexcell$, the vertices of which are the line intersections, and the hyperedges are vertices of a cell. Analogously, we consider the problem of touching the lines with a minimum subset of the cells of the arrangement, which we identify as the minimum vertex cover problem in the $\Hcellzone$ hypergraph.
On additive combinatorics of permutations of ℤn
Authors: Chandran L. Sunil , Rajendraprasad Deepak , Singh Nitin
Published: August 2021

Special issue PRIMA 2013

Let ℤn denote the ring of integers modulo n. A permutation of ℤn is a sequence of n distinct elements of ℤn. Addition and subtraction of two permutations is defined element-wise. In this paper we consider two extremal problems on permutations of ℤn, namely, the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is again a permutation, and the maximum size of a collection of permutations such that no sum of two distinct permutations in the collection is a permutation. Let the sizes be denoted by s(n) and t(n) respectively. The case when n is even is trivial in both the cases, with s(n)=1 and t(n)=n!. For n odd, we prove (nφ(n))/2k≤s(n)≤n!· 2-(n-1)/2((n-1)/2)! and 2(n-1)/2·(n-1 / 2)!≤t(n)≤ 2k·(n-1)!/φ(n), where k is the number of distinct prime divisors of n and φ is the Euler's totient function.
A matroid associated with a phylogenetic tree
Authors: Dress Andreas , Huber Katharina , Steel Mike
Published: August 2021

Special issue PRIMA 2013

A (pseudo-)metric D on a finite set X is said to be a \textquotelefttree metric\textquoteright if there is a finite tree with leaf set X and non-negative edge weights so that, for all x,y ∈X, D(x,y) is the path distance in the tree between x and y. It is well known that not every metric is a tree metric. However, when some such tree exists, one can always find one whose interior edges have strictly positive edge weights and that has no vertices of degree 2, any such tree is – up to canonical isomorphism – uniquely determined by D, and one does not even need all of the distances in order to fully (re-)construct the tree\textquoterights edge weights in this case. Thus, it seems of some interest to investigate which subsets of X, 2 suffice to determine (\textquoteleftlasso\textquoteright) these edge weights. In this paper, we use the results of a previous paper to discuss the structure of a matroid that can be associated with an (unweighted) X-tree T defined by the requirement that its bases are exactly the \textquotelefttight edge-weight lassos\textquoteright for T, i.e, the minimal subsets of X, 2 that lasso the edge weights of T.
Hamiltonian decomposition of prisms over cubic graphs
Authors: Rosenfeld Moshe , Xiang Ziqing
Published: August 2021

Special issue PRIMA 2013

The prisms over cubic graphs are 4-regular graphs. The prisms over 3-connected cubic graphs are Hamiltonian. In 1986 Brian Alspach and Moshe Rosenfeld conjectured that these prisms are Hamiltonian decomposable. In this paper we present a short survey of the status of this conjecture, various constructions proving that certain families of prisms over 3-connected cubic graphs are Hamiltonian decomposable. Among others, we prove that the prisms over cubic Halin graphs, cubic generalized Halin graphs of order 4k + 2 and other infinite sequences of cubic graphs are Hamiltonian decomposable.
Determining pure discrete spectrum for some self-affine tilings
Authors: Akiyama Shigeki , Gähler Franz , Lee Jeong-Yup
Published: August 2021

Discrete Algorithms

By the algorithm implemented in the paper by Akiyama-Lee [Adv. Math. 226(4):2855 13;2883, 2011] and some of its predecessors, we have examined the pure discreteness of the spectrum for all irreducible Pisot substitutions of trace less than or equal to 2, and some cases of planar tilings generated by boundary substitutions due to Kenyon [Geom. Func. Anal. 6:471 13;488, 1996].
Oriented diameter and rainbow connection number of a graph
Authors: Huang Xiaolong , Li Hengzhe , Li Xueliang , Sun Yuefang
Published: August 2021

Graph Theory

The oriented diameter of a bridgeless graph G is min diam(H) | H is a strang orientation of G. A path in an edge-colored graph G, where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer number k for which there exists a k-edge-coloring of G such that every two distinct vertices of G are connected by a rainbow path. In this paper, we obtain upper bounds for the oriented diameter and the rainbow connection number of a graph in terms of rad(G) and η(G), where rad(G) is the radius of G and η(G) is the smallest integer number such that every edge of G is contained in a cycle of length at most η(G). We also obtain constant bounds of the oriented diameter and the rainbow connection number for a (bipartite) graph G in terms of the minimum degree of G.
Maximum difference about the size of optimal identifying codes in graphs differing by one vertex
Authors: Pelto Mikko
Published: August 2021

Graph Theory

Let G=(V,E) be a simple undirected graph. We call any subset C⊆V an identifying code if the sets I(v)={c∈C | {v,c}∈E or v=c } are distinct and non-empty for all vertices v∈V. A graph is called twin-free if there is an identifying code in the graph. The identifying code with minimum size in a twin-free graph G is called the optimal identifying code and the size of such a code is denoted by γ(G). Let GS denote the induced subgraph of G where the vertex set S⊂V is deleted. We provide a tight upper bound for γ(GS)-γ(G) when both graphs are twin-free and |V| is large enough with respect to |S|. Moreover, we prove tight upper bound when G is a bipartite graph and |S|=1.
How often should you clean your room?
Authors: Martin Kimball , Shankar Krishnan
Published: August 2021

Analysis of Algorithms

We introduce and study a combinatorial optimization problem motivated by the question in the title. In the simple case where you use all objects in your room equally often, we investigate asymptotics of the optimal time to clean up in terms of the number of objects in your room. In particular, we prove a logarithmic upper bound, solve an approximate version of this problem, and conjecture a precise logarithmic asymptotic.
Connectivity of Fibonacci cubes, Lucas cubes and generalized cubes
Authors: Azarija Jernej , Klavžar Sandi , Lee Jaehun , Rho Yoomi
Published: August 2021

Graph Theory

If f is a binary word and d a positive integer, then the generalized Fibonacci cube Qd(f) is the graph obtained from the d-cube Qd by removing all the vertices that contain f as a factor, while the generalized Lucas cube Qd(lucas(f)) is the graph obtained from Qd by removing all the vertices that have a circulation containing f as a factor. The Fibonacci cube Γd and the Lucas cube Λd are the graphs Qd(11) and Qd(lucas(11)), respectively. It is proved that the connectivity and the edge-connectivity of Γd as well as of Λd are equal to ⌊ d+2 / 3⌋. Connected generalized Lucas cubes are characterized and generalized Fibonacci cubes are proved to be 2-connected. It is asked whether the connectivity equals minimum degree also for all generalized Fibonacci/Lucas cubes. It was checked by computer that the answer is positive for all f and all d≤9.
On the 1-2-3-conjecture
Authors: Davoodi Akbar , Omoomi Behnaz
Published: August 2021

Graph Theory

A k-edge-weighting of a graph G is a function w:E(G)→{1,…,k}. An edge-weighting naturally induces a vertex coloring c, where for every vertex v∈V(G), c(v)=∑e∼vw(e). If the induced coloring c is a proper vertex coloring, then w is called a vertex-coloring k-edge-weighting (VC k-EW). Karoński et al. (J. Combin. Theory Ser. B, 91 (2004) 151 13;157) conjectured that every graph admits a VC 3-EW. This conjecture is known as the 1-2-3-conjecture. In this paper, first, we study the vertex-coloring edge-weighting of the Cartesian product of graphs. We prove that if the 1-2-3-conjecture holds for two graphs G and H, then it also holds for G□H. Also we prove that the Cartesian product of connected bipartite graphs admits a VC 2-EW. Moreover, we present several sufficient conditions for a graph to admit a VC 2-EW. Finally, we explore some bipartite graphs which do not admit a VC 2-EW.
Edge stability in secure graph domination
Authors: Burger Anton Pierre , Villiers Alewyn Petrus , Vuuren Jan Harm
Published: August 2021

Graph Theory

A subset X of the vertex set of a graph G is a secure dominating set of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X-v)∪u is again a dominating set of G. The secure domination number of G is the cardinality of a smallest secure dominating set of G. A graph G is p-stable if the largest arbitrary subset of edges whose removal from G does not increase the secure domination number of the resulting graph, has cardinality p. In this paper we study the problem of computing p-stable graphs for all admissible values of p and determine the exact values of p for which members of various infinite classes of graphs are p-stable. We also consider the problem of determining analytically the largest value ωn of p for which a graph of order n can be p-stable. We conjecture that ωn=n-2 and motivate this conjecture.
On probe 2-clique graphs and probe diamond-free graphs
Authors: Bonomo Flavia , Figueiredo Celina M. H. , Duran Guillermo , Grippo Luciano N. , Safe Martín D. , Szwarcfiter Jayme L.
Published: August 2021

Graph Theory

Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that non-edges of G, whose endpoints are nonprobe vertices, can be added so that the resulting graph belongs to G. We investigate probe 2-clique graphs and probe diamond-free graphs. For probe 2-clique graphs, we present a polynomial-time recognition algorithm. Probe diamond-free graphs are characterized by minimal forbidden induced subgraphs. As a by-product, it is proved that the class of probe block graphs is the intersection between the classes of chordal graphs and probe diamond-free graphs.
Guarded subgraphs and the domination game
Authors: Brešar Boštjan , Klavžar Sandi , Košmrlj Gasper , Rall Doug F.
Published: August 2021

Graph Theory

We introduce the concept of guarded subgraph of a graph, which as a condition lies between convex and 2-isometric subgraphs and is not comparable to isometric subgraphs. Some basic metric properties of guarded subgraphs are obtained, and then this concept is applied to the domination game. In this game two players, Dominator and Staller, alternate choosing vertices of a graph, one at a time, such that each chosen vertex enlarges the set of vertices dominated so far. The aim of Dominator is that the graph is dominated in as few steps as possible, while the aim of Staller is just the opposite. The game domination number is the number of vertices chosen when Dominator starts the game and both players play optimally. The main result of this paper is that the game domination number of a graph is not smaller than the game domination number of any guarded subgraph. Several applications of this result are presented.
Ore-degree threshold for the square of a Hamiltonian cycle
Authors: DeBiasio Louis , Faizullah Safi , Khan Imdadullah
Published: August 2021

Graph Theory

A classic theorem of Dirac from 1952 states that every graph with minimum degree at least n=2 contains a Hamiltonian cycle. In 1963, P´osa conjectured that every graph with minimum degree at least 2n=3 contains the square of a Hamiltonian cycle. In 1960, Ore relaxed the degree condition in the Dirac’s theorem by proving that every graph with deg(u) + deg(v) ≥ n for every uv =2 E(G) contains a Hamiltonian cycle. Recently, Chˆau proved an Ore-type version of P´osa’s conjecture for graphs on n ≥ n0 vertices using the regularity–blow-up method; consequently the n0 is very large (involving a tower function). Here we present another proof that avoids the use of the regularity lemma. Aside from the fact that our proof holds for much smaller n0, we believe that our method of proof will be of independent interest.
Packing Plane Perfect Matchings into a Point Set
Authors: Biniaz Ahmad , Bose Prosenjit , Maheshwari Anil , Smid Michiel
Published: August 2021

Given a set $P$ of $n$ points in the plane, where $n$ is even, we consider the following question: How many plane perfect matchings can be packed into $P$? For points in general position we prove the lower bound of ⌊log2$n$⌋$-1$. For some special configurations of point sets, we give the exact answer. We also consider some restricted variants of this problem.
Reducing the rank of a matroid
Authors: Joret Gwenaël , Vetta Adrian
Published: August 2021

We consider the rank reduction problem for matroids: Given a matroid $M$ and an integer $k$, find a minimum size subset of elements of $M$ whose removal reduces the rank of $M$ by at least $k$. When $M$ is a graphical matroid this problem is the minimum $k$-cut problem, which admits a 2-approximation algorithm. In this paper we show that the rank reduction problem for transversal matroids is essentially at least as hard to approximate as the densest $k$-subgraph problem. We also prove that, while the problem is easily solvable in polynomial time for partition matroids, it is NP-hard when considering the intersection of two partition matroids. Our proof shows, in particular, that the maximum vertex cover problem is NP-hard on bipartite graphs, which answers an open problem of B. Simeone.
Minimum Number of Colors: the Turk’s Head Knots Case Study
Authors: Lopes Pedro , Matias João
Published: August 2021

An $r$-coloring of a knot diagram is an assignment of integers modulo $r$ to the arcs of the diagram such that at each crossing, twice the the number assigned to the over-arc equals the sum of the numbers assigned to the under-arcs, modulo $r$. The number of $r$-colorings is a knot invariant i.e., for each knot, it does not depend on the diagram we are using for counting them. In this article we calculate the number of $r$-colorings for the so-called Turk's Head Knots, for each modulus $r$. Furthermore, it is also known that whenever a knot admits an $r$-coloring using more than one color then all other diagrams of the same knot admit such $r$-colorings (called non-trivial $r$-colorings). This leads to the question of what is the minimum number of colors it takes to assemble such an $r$-coloring for the knot at issue. In this article we also estimate and sometimes calculate exactly what is the minimum numbers of colors for each of the Turk's Head Knots, for each relevant modulus $r$.
Symmetries of Monocoronal Tilings
Authors: Frettlöh Dirk , Garber Alexey
Published: August 2021

The vertex corona of a vertex of some tiling is the vertex together with the adjacent tiles. A tiling where all vertex coronae are congruent is called monocoronal. We provide a classification of monocoronal tilings in the Euclidean plane and derive a list of all possible symmetry groups of monocoronal tilings. In particular, any monocoronal tiling with respect to direct congruence is crystallographic, whereas any monocoronal tiling with respect to congruence (reflections allowed) is either crystallographic or it has a one-dimensional translation group. Furthermore, bounds on the number of the dimensions of the translation group of monocoronal tilings in higher dimensional Euclidean space are obtained.
The inapproximability for the $(0,1)$-additive number
Authors: Ahadi Arash , Dehghan Ali
Published: August 2021

An additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$ ($x \sim y$ means that $x$ is joined to $y$). The additive number of $G$, denoted by $\eta (G)$, is the minimum number $k$ such that $G$ has a additive labeling $\ell : V(G) \rightarrow \mathbb{N}_k$. The additive choosability of a graph $G$, denoted by $\eta_\ell (G)$, is the smallest number $k$ such that $G$ has an additive labeling for any assignment of lists of size $k$ to the vertices of $G$, such that the label of each vertex belongs to its own list. Seamone in his PhD thesis conjectured that for every graph $G$, $\eta(G)= \eta_\ell (G)$. We give a negative answer to this conjecture and we show that for every $k$ there is a graph $G$ such that $\eta_\ell (G) - \eta(G) \geq k$. A $(0,1)$-additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \{0,1 \}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$. A graph may lack any $(0,1)$-additive labeling. We show that it is NP-complete to decide whether a $(0,1)$-additive labeling exists for some families of graphs such as perfect graphs and planar triangle-free graphs. For a graph $G$ with some $(0,1)$-additive labelings, the $(0,1)$-additive number of $G$ is defined as $\sigma_1 (G) = \mathrm{min}_{\ell \in \Gamma} \Sigma_{v \in V (G)} \ell (v)$ where $\Gamma$ is the set of $(0,1)$-additive labelings of $G$. We prove that given a planar graph that admits a $(0,1)$-additive labeling, for all $\epsilon > 0$ , approximating the $(0,1)$-additive number within $n^{1-\epsilon}$ is NP-hard.
Planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable
Authors: Bonamy Marthe , Lévêque Benjamin , Pinlou Alexandre
Published: August 2021

For planar graphs, we consider the problems of list edge coloring and list total coloring. Edge coloring is the problem of coloring the edges while ensuring that two edges that are adjacent receive different colors. Total coloring is the problem of coloring the edges and the vertices while ensuring that two edges that are adjacent, two vertices that are adjacent, or a vertex and an edge that are incident receive different colors. In their list extensions, instead of having the same set of colors for the whole graph, every vertex or edge is assigned some set of colors and has to be colored from it. A graph is minimally edge or total choosable if it is list $\Delta$-edge-colorable or list $(\Delta +1)$-total-colorable, respectively, where $\Delta$ is the maximum degree in the graph. It is already known that planar graphs with $\Delta \geq 8$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable (Li Xu 2011), and that planar graphs with $\Delta \geq 7$ and no triangle sharing a vertex with a $C_4$ or no triangle adjacent to a $C_k (\forall 3 \leq k \leq 6)$ are minimally total colorable (Wang Wu 2011). We strengthen here these results and prove that planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable.
Statistics for 3-letter patterns with repetitions in compositions
Authors: Shabani Armend , Gjergji Rexhep
Published: August 2021

A composition $\pi = \pi_1 \pi_2 \cdots \pi_m$ of a positive integer $n$ is an ordered collection of one or more positive integers whose sum is $n$. The number of summands, namely $m$, is called the number of parts of $\pi$. Using linear algebra, we determine formulas for generating functions that count compositions of $n$ with $m$ parts, according to the number of occurrences of the subword pattern $\tau$, and according to the sum, over all occurrences of $\tau$, of the first integers in their respective occurrences, where $\tau$ is any pattern of length three with exactly 2 distinct letters.
Dendriform structures for restriction-deletion and restriction-contraction matroid Hopf algebras
Authors: Hoang-Nghia Nguyen , Tanasa Adrian , Tollu Christophe
Published: August 2021

We endow the set of isomorphism classes of matroids with a new Hopf algebra structure, in which the coproduct is implemented via the combinatorial operations of restriction and deletion. We also initiate the investigation of dendriform coalgebra structures on matroids and introduce a monomial invariant which satisfy a convolution identity with respect to restriction and deletion.
Energy-optimal algorithms for computing aggregative functions in random networks
Authors: Klonowski Marek , Sulkowska Małgorzata
Published: August 2021

We investigate a family of algorithms minimizing energetic effort in random networks computing aggregative functions. In contrast to previously considered models, our results minimize maximal energetic effort over all stations instead of the average usage of energy. Such approach seems to be much more suitable for some kinds of networks, in particular ad hoc radio networks, wherein we need all stations functioning and replacing batteries after the deployment is not feasible. We analyze also the latency of proposed energy-optimal algorithms. We model a network by placing randomly and independently $n$ points in a $d$-dimensional cube of side-length $n^{1/d}$. We place an edge between vertices that interact with each other. We analyze properties of the resulting graphs in order to obtain estimates on energetic effort and latency of proposed algorithms.
Robust Wireless Sensor Network Deployment
Authors: Erdelj Milan , Mitton Nathalie , Razafindralambo Tahiry
Published: August 2021

In this work we present a decentralized deployment algorithm for wireless mobile sensor networks focused on deployment Efficiency, connectivity Maintenance and network Reparation (EMR). We assume that a group of mobile sensors is placed in the area of interest to be covered, without any prior knowledge of the environment. The goal of the algorithm is to maximize the covered area and cope with sudden sensor failures. By relying on the locally available information regarding the environment and neighborhood, and without the need for any kind of synchronization in the network, each sensor iteratively chooses the next-step movement location so as to form a hexagonal lattice grid. Relying on the graph of wireless mobile sensors, we are able to provide the properties regarding the quality of coverage, the connectivity of the graph and the termination of the algorithm. We run extensive simulations to provide compactness properties of the deployment and evaluate the robustness against sensor failures. We show through the analysis and the simulations that EMR algorithm is robust to node failures and can restore the lattice grid. We also show that even after a failure, EMR algorithm call still provide a compact deployment in a reasonable time.
Performance Evaluation of Demodulation Methods: a Combinatorial Approach
Authors: Krob Daniel , Vassilieva Ekaterina A.
Published: August 2021

This paper provides a combinatorial approach for analyzing the performance of demodulation methods used in GSM. We also show how to obtain combinatorially a nice specialization of an important performance evaluation formula, using its connection with a classical bijection of Knuth between pairs of Young tableaux and {0,1}-matrices.
On the Toppling of a Sand Pile
Authors: Novelli Jean-Christophe , Rossin Dominique
Published: August 2021

In this paper, we provide the first study of the sand pile model SPM(0) where we assume that all the grains are numbered with a distinct integer.We obtain a lower bound on the number of terminal sand piles by establishing a bijection between a subset of these sand piles and the set of shifted Young tableaux. We then prove that this number is at least factorial.
Tilings of a Domain on a Hexagon Mesh with Balanced 3-Tiles
Authors: Radenne Gilles
Published: August 2021

In this article, we study the question of tilings on a hexagon mesh with balanced 3-tiles. This problem has been studied by Conway and Lagarias in [CL90], by studying the tiling groups, in fact a group containing the tiling-groups, and their Cayley graphs. We will use two different approaches. The first one is based on matchings in bipartite graphs, which in this case are in correspondance with tilings of domains by lozenges, and thus can be efficiently studied, using Thurston's algorithm (see [Thu90]). The second one is based on a color and balancing approach of Thurston's algorithm, exposed in [Fou96].
New Bounds for Hypercube Slicing Numbers
Authors: Emamy-Khansary M. Reza , Ziegler Martin
Published: August 2021

What is the maximum number of edges of the d-dimensional hypercube, denoted by S(d,k), that can be sliced by k hyperplanes? This question on combinatorial properties of Euclidean geometry arising from linear separability considerations in the theory of Perceptrons has become an issue on its own. We use computational and combinatorial methods to obtain new bounds for S(d,k), d ≤ 8. These strengthen earlier results on hypercube cut numbers.