Search

As an analog of intersection graphs among digraphs, catch digraphs were introduced by Hiroshi Maehara in 1984. Later on, Prisner focused his research on interval catch digraphs, which he identified as diasteroidal triple free digraphs. It has been used to solve a variety of real-world challenges, such as networking, telecommunication operations, traffic control, and location problems. Oriented catch digraphs are those catch digraphs that have exactly one edge direction attached to each edge of the corresponding underlying graph. In this article, we consider two important subclasses of oriented catch digraphs, namely, oriented interval catch digraphs and oriented circular-arc catch digraphs. First, we characterize those oriented interval catch digraphs whose underlying graphs are trees in terms of forbidden subdigraphs. Next, we provide a characterization of connected proper oriented interval catch digraphs whose underlying graphs are chordal, by determining the complete list of forbidden induced subdigraphs. Another interesting result is characterizing oriented circular-arc catch digraphs, which are tournaments. [ABSTRACT FROM AUTHOR]

Efficient vectors are the natural set from which to choose a cardinal ranking vector for a pairwise comparison matrix. Such vectors are the key to certain business project selection models. Many ways to construct specific efficient vectors have been proposed. Yet, no previous method to produce all efficient vectors was known. Here, using some graph theoretic ideas, as well as a numerical extension technique, we show how to generate inductively all efficient vectors for any given pairwise comparison matrix. We apply this method to give a matricial proof of the fact that the set of efficient vectors, as well as some of its important subsets, are piecewise linearly connected. In addition, we determine explicitly all efficient vectors for a 4-by-4 pairwise comparison matrix. Several examples are provided. [ABSTRACT FROM AUTHOR]

For a real number q > 0 , the q-th outdegree power of a digraph D is ∂ q + (D) = ∑ v ∈ V (G) (d D + (v)) q . For a graph G, D (G) is the set of all orientations of G. We focus on a fundamental problem on deciding min { ∂ q + (D) : D ∈ D (G) } and max { ∂ q + (D) : D ∈ D (G) } . The extremal values for a complete multipartite graph are determined, answering a question posed by Xu et al. (Appl Math Comput 433:127414, 2022). The sharp lower and upper bounds for ∂ q + (D) are obtained for graphs G with fixed order and size, where D is any orientation of G. In addition, the sharp lower and upper bounds for ∂ q + (D) are obtained for a graph G with fixed order and connectivity, where D is any orientation of G. [ABSTRACT FROM AUTHOR]

This paper introduces the concepts of spectral influence and spectral cyclicality, both derived from the largest eigenvalue of a graph’s adjacency matrix. These two novel centrality measures capture both diffusion and interdependence from a local and global perspective respectively. We propose a new clustering algorithm that identifies communities with high cyclicality and interdependence, allowing for overlaps. To illustrate our method, we apply it to input-output analysis within the context of the Moroccan economy. [ABSTRACT FROM AUTHOR]

Our contribution is twofold: (1) We formulate and solve a particular graph-theoretic problem: For an undirected graph G admitting a so-called MB-good orientation (acyclic with all its sources and sinks having degree at most 2), we calculate the minimum number ν (G) of “transit” vertices (neither sources nor sinks) of degree 2 over all MB-good orientations of G. Surprisingly, ν (G) ≤ 1 , and for most graphs, there exist MB-good orientations with all vertices of degree 2 being sources or sinks, i.e., with ν (G) = 0 . As an application, (2) in the context of the Reeb graph theory, we characterize the set of Reeb graphs defined by all Morse–Bott functions on a given surface; namely, we prove a criterion on realization of a graph as the Reeb graph of a Morse–Bott function on this surface. [ABSTRACT FROM AUTHOR]

It is well-known that every tournament contains a Hamilton path, and every strongly connected tournament contains a Hamilton cycle. This paper establishes transversal generalizations of these classical results. For a collection T = (T 1 , ⋯ , T m) of not-necessarily distinct tournaments on a common vertex set V, an m-edge directed graph D with vertices in V is called a T -transversal if there exists a bijection ϕ : E (D) → [ m ] such that e ∈ E (T ϕ (e)) for all e ∈ E (D) . We prove that for sufficiently large m with m = | V | - 1 , there exists a T -transversal Hamilton path. Moreover, if m = | V | and at least m - 1 of the tournaments T 1 , ... , T m are assumed to be strongly connected, then there is a T -transversal Hamilton cycle. In our proof, we utilize a novel way of partitioning tournaments which we dub H -partition. [ABSTRACT FROM AUTHOR]

Let Γ be a graph with vertex set V, and let a, b be nonnegative integers. An (a, b)-regular set in Γ is a nonempty proper subset D of V such that every vertex in D has exactly a neighbours in D and every vertex in V \ D has exactly b neighbours in D. In particular, a (1, 1)-regular set is called a total perfect code. Let G be a finite group and S a square-free subset of G closed under conjugation. The Cayley sum graph CayS (G , S) of G is the graph with vertex set G such that two vertices x, y are adjacent if and only if x y ∈ S . A subset (respectively, subgroup) D of G is called an (a, b)-regular set (respectively, subgroup (a, b)-regular set) of G if there exists a Cayley sum graph of G which admits D as an (a, b)-regular set. We obtain two necessary and sufficient conditions for a subgroup of a finite group G to be a total perfect code in a Cayley sum graph of G. We also obtain two necessary and sufficient conditions for a subgroup of a finite abelian group G to be a total perfect code of G. We classify finite abelian groups whose all non-trivial subgroups of even order are total perfect codes of the group, and as a corollary we obtain that a finite abelian group has the property that every non-trivial subgroup is a total perfect code if and only if it is isomorphic to an elementary abelian 2-group. We prove that, for a subgroup H of a finite abelian group G and any pair of positive integers (a, b) within certain ranges depending on H, H is an (a, b)-regular set of G if and only if it is a total perfect code of G. Finally, we give a classification of subgroup total perfect codes of a cyclic group, a dihedral group and a generalized quaternion group. [ABSTRACT FROM AUTHOR]

We show that for every $\eta \gt 0$ every sufficiently large $n$ -vertex oriented graph $D$ of minimum semidegree exceeding $(1+\eta)\frac k2$ contains every balanced antidirected tree with $k$ edges and bounded maximum degree, if $k\ge \eta n$. In particular, this asymptotically confirms a conjecture of the first author for long antidirected paths and dense digraphs. Further, we show that in the same setting, $D$ contains every $k$ -edge antidirected subdivision of a sufficiently small complete graph, if the paths of the subdivision that have length $1$ or $2$ span a forest. As a special case, we can find all antidirected cycles of length at most $k$. Finally, we address a conjecture of Addario-Berry, Havet, Linhares Sales, Reed, and Thomassé for antidirected trees in digraphs. We show that this conjecture is asymptotically true in $n$ -vertex oriented graphs for all balanced antidirected trees of bounded maximum degree and of size linear in $n$. [ABSTRACT FROM AUTHOR]

Let GG be a graph. Then, the inverse graph G−1{G}^{-1} of GG is defined to be a graph that has adjacency matrix similar to the inverse of the adjacency matrix of GG, where the similarity matrix is ±1\pm 1 diagonal matrix. In this article, we introduced a generalization of this definition that serves the mixed graphs where the definition applied for the α\alpha -Hermitian adjacency matrices of mixed graphs. Furthermore, for a class of unicyclic graphs, we were able to find an inverse mixed graph for a graph GG, where it was proven that G−1{G}^{-1} does not exist.

We only consider finite structures. With every totally ordered set V and a subset P of V 2 , we associate the underlying tournament Inv (V ̲ , P) obtained from the transitive tournament V ̲ : = (V , { (x , y) ∈ V × V : x < y }) by reversing P, i.e., by reversing the arcs (x, y) such that { x , y } ∈ P . The subset P is a pairing (of ∪ P ) if | ∪ P | = 2 | P | , a quasi-pairing (of ∪ P ) if | ∪ P | = 2 | P | - 1 ; it is irreducible if no nontrivial interval of ∪ P is a union of connected components of the graph (∪ P , P) . In this paper, we consider pairings and quasi-pairings in relation to tournaments. We establish close relationships between irreducibility of pairings (or quasi-pairings) and indecomposability of their underlying tournaments under modular decomposition. For example, given a pairing P of a totally ordered set V of size at least 6, the pairing P is irreducible if and only if the tournament Inv (V ̲ , P) is indecomposable. This is a consequence of a more general result characterizing indecomposable tournaments obtained from transitive tournaments by reversing pairings. We obtain analogous results in the case of quasi-pairings. [ABSTRACT FROM AUTHOR]

In the wake of Dutta and Adhikari, who in 2020 used partial transposition in order to get pairs of cospectral graphs, we investigate partial transposition for Hermitian complex matrices. This allows us to construct infinite pairs of complex unit gain graphs (or T -gain graphs) sharing either the spectrum of the adjacency matrix or even the spectrum of all the generalized adjacency matrices. This investigation also sheds new light on the classical case, producing examples that were still missing even for graphs. Partial transposition requires a block structure of the matrix: we interpreted it as if coming from a composition of T -gain digraphs. By proposing a suitable definition of rigidity specifically for T -gain digraphs, we then produce the first examples of pairs of non-isomorphic graphs, signed graphs and T -gain graphs obtained via partial transposition of matrices whose blocks form families of commuting normal matrices. In some cases, the non-isomorphic graphs detected in this way turned out to be hardly distinguishable, since they share the adjacency, the Laplacian and the signless Laplacian spectrum, together with many non-spectral graph invariants. [ABSTRACT FROM AUTHOR]

The Terwilliger algebras of asymmetric association schemes of rank 3, whose nonidentity relations correspond to doubly regular tournaments, are shown to have thin irreducible modules, and to always be of dimension 4 k + 9 for some positive integer k. It is determined that asymmetric rank 3 association schemes of order up to 23 are determined up to combinatorial isomorphism by the list of their complex Terwilliger algebras at each vertex, but this is no longer true at order 27. To distinguish order 27 asymmetric rank 3 association schemes, it is shown using computer calculations that the list of rational Terwilliger algebras at each vertex will suffice. [ABSTRACT FROM AUTHOR]

The stable index of a 0–1 matrix A is defined to be the smallest integer k such that $ A^{k+1} $ A k + 1 is not a 0–1 matrix if such an integer exists; otherwise the stable index of A is defined to be infinity. We characterize the set of stable indices of 0–1 matrices with a given order. [ABSTRACT FROM AUTHOR]

We construct 2-step nilpotent Lie algebras using labeled directed simple graphs and give a criterion to detect certain ideals and subalgebras by finding special subgraphs. We prove that if a label occurs only once, then reversing its orientation leads to an isomorphic algebra. As a consequence, if every edge is labeled differently, the Lie algebra depends only on the underlying undirected graph. In addition, we construct the graphs of all 2-step nilpotent Lie algebras of dimension ≤ 6 and compute the algebra of strata preserving derivations of the Lie algebra associated with the complete bipartite graph K m , n with two different labelings. [ABSTRACT FROM AUTHOR]

It was recently shown that a large class of phylogenetic networks, the ‘labellable’ networks, is in bijection with the set of ‘expanding’ covers of finite sets. In this paper, we show how several prominent classes of phylogenetic networks can be characterised purely in terms of properties of their associated covers. These classes include the tree-based, tree-child, orchard, tree-sibling, and normal networks. In the opposite direction, we give an example of how a restriction on the set of expanding covers can define a new class of networks, which we call ‘spinal’ phylogenetic networks. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph that represents an underlying network. Let τ (resp. p ) be an assignment of non-negative integers as thresholds (resp. incentives) to the vertices of G. The discrete time activation process with incentives corresponding to (G , τ , p) is the following. First, all vertices u with p (u) ≥ τ (u) are activated. Then at each time t, every vertex u gets activated if the number of previously activated neighbors of u plus p (u) is at least τ (v) . The optimal target vector problem (OTV) is to find the minimum total incentives ∑ v ∈ V p (v) that activates the whole network. We extend this model of activation with incentives, for graphs with weighted edges such that the spread of activation in the network depends on the weight of influence between any two participants. The new version is more realistic for the real world networks. We first prove that the new problem OTVW, is NP -complete even for the complete graphs. Two lower bounds for the minimum total incentives are presented. Next, we prove that OTVW has polynomial time solutions for (weighted) path and cycle graphs. Finally, we extend the discussed model and OTV, for bi-directed graphs with weighted edges and prove that to obtain the optimal target vector in weighted bi-directed paths and cycles has polynomial time solutions. [ABSTRACT FROM AUTHOR]

In this paper, we give constructions of self-orthogonal codes from orbit matrices of Deza graphs, normally regular digraphs and Deza digraphs in terms of a definition given by Wang and Feng. These constructions can also be applied to adjacency matrices of the mentioned graphs. Since a lot of constructions of Deza graphs, normally regular digraphs and Deza digraphs in the sense of Wang and Feng have been known, the methods presented in this paper give us a rich source of matrices that span self-orthogonal codes. [ABSTRACT FROM AUTHOR]

We give a new elementary proof of El Sahili conjecture El Sahili (Discrete Math 287:151–153, 2004) stating that any n-chromatic digraph D, with n ≥ 4 , contains a path with two blocks of order n. [ABSTRACT FROM AUTHOR]

Two binary relational structures of a same signature are (≤ k)-hypomorphic if they have the same vertex set and their restrictions to each set of at most k vertices are isomorphic. A binary relational structure is (≤ k)-reconstructible if it is isomorphic with each structure it is (≤ k)-hypomorphic with. We establish an inductive characterisation of pairs of (≤ 3)-hypomorphic binary relational structures (under some slight restriction). We infer a characterisation of (≤ 3)-reconstructibility for bi-founded binary relational structures. A binary relational structure is bi-founded if it has no infinite set of pairwise comparable strong modules. On the one hand, we describe operations generating exactly the class of (≤ 3)-reconstructible bi-founded binary relational structures from singleton ones. On the other hand, this characterisation can be formulated in terms of restrictions on the structuration of the tree of robust modules of the structure. This allows in particular the extension of Boudabbous and Lopez (Discrete Math. 291, 19–40, 3): a bi-founded tournament is(≤ 3)-reconstructibleif and only if all its modules are selfdual. Furthermore we show that the restrictions on structuration above do not characterise (≤ 3)-reconstructibility on any of the following two classes, of which the class of bi-founded structures is the intersection, namely the class of founded structures (the class of structures the collection of strong modules of which is well-founded for inclusion), and the class of co-founded structures (the class of structures the collection of strong modules of which is well-founded for the reverse of inclusion, equivalently every strong module of which is robust, corresponding to [15]'s class of completely decomposable structures). Indeed we provide examples of founded, resp. co-founded, non (≤ 3)-reconstructible tournaments every module of which is selfdual. [ABSTRACT FROM AUTHOR]

The present article introduces the notion of marked rhythm and its almost smoothness through a certain transformation Rep, called repulsion map. A marked rhythm consists of a rhythm together with a marker, and the map Rep modifies the marked onset of the rhythm. It is shown that an iteration of the map Rep transforms an arbitrary marked rhythm into an almost smooth one. A numerical criterion for a marked rhythm to be almost smooth is given in terms of the difference of its rhythm part. Smooth rhythms are shown to be always almost smooth, and several examples of almost smooth but not smooth rhythms are constructed. [ABSTRACT FROM AUTHOR]