Search

Let G : = (G 1 , G 2 , G 3) be a triple of graphs on the same vertex set V of size n. A rainbow triangle in G is a triple of edges (e 1 , e 2 , e 3) with e i ∈ G i for each i and { e 1 , e 2 , e 3 } forming a triangle in V. The triples G not containing rainbow triangles, also known as Gallai colouring templates, are a widely studied class of objects in extremal combinatorics. In the present work, we fully determine the set of edge densities (α 1 , α 2 , α 3) such that if | E (G i) | > α i n 2 for each i and n is sufficiently large, then G must contain a rainbow triangle. This resolves a problem raised by Aharoni, DeVos, de la Maza, Montejanos and Šámal, generalises several previous results on extremal Gallai colouring templates, and proves a recent conjecture of Frankl, Győri, He, Lv, Salia, Tompkins, Varga and Zhu. [ABSTRACT FROM AUTHOR]

This paper extends the framework of soft set theory to directed graphs by introducing and analyzing the concepts of the normal product and restricted normal product of soft directed graphs. Building on Molodtsov’s foundational work in developing soft set theory to address uncertainty in data, this study presents new methods for modeling and understanding complex systems where uncertainty plays a significant role. Soft directed graphs, which enhance traditional graph models by incorporating parameters and uncertain relationships, serve as the foundation for this investigation. The normal product, defined as a combination of two soft directed graphs based on their respective parameter sets, and the restricted normal product, which combines soft directed graphs only where their parameter sets intersect, provide a comprehensive framework for these new operations. This paper also establishes the structural properties of these products, ensuring they are well-defined and retain the key features of soft directed graphs. Furthermore, we derive combinatorial identities related to vertex and arc counts, as well as degree sums, offering deeper insights into the composition and behavior of these graph products. [ABSTRACT FROM AUTHOR]

One important algebraic invariant in networks is complexity. This invariant ensures the accuracy and dependability of the network. In this paper, we employ a combinatorial approach to determine the graph's complexity. A fundamental set of building blocks (basic graphs) will serve as the foundation for all the graphs we investigate, after which we will analyze the individual blocks and the ways in which they are connected. We compute the spectrum and complexity of a number of fundamental graphs and then we employ the novel duplication corona and Cartesian product operations to construct advanced networks from these graphs. Specifically, straightforward formulas are derived for the complexity of the networks created by the new duplicating corona of the regular graphs (prism, diagonal prism, cycle, complete graph, shadow of the cycle, and Petersen graph) with some families of graphs. Furthermore, using Cartesian product operation, evident and specific formulas for the complexity of the prism of the grid graph Gl,κ, the prism of the stacked book graph Bl,s, the diagonal plane prism grid graph, and the prism of the cylindrical graph Cl,κ are derived. [ABSTRACT FROM AUTHOR]

For any hereditary graph class F, we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in F. As a consequence, we show that, if F admits efficient adjacency labels (or, equivalently, small induced-universal graphs) meeting the information-theoretic minimum, then the classes of subgraphs and induced subgraphs of Cartesian products of graphs in F do too. Our proof uses ideas from randomized communication complexity, hashing, and additive combinatorics, and improves upon recent results of Chepoi, Labourel, and Ratel [Journal of Graph Theory, 2020]. [ABSTRACT FROM AUTHOR]

Feynman diagrams represent one of the most powerful and fascinating tools developed in theoretical physics in the last century. Introduced within the framework of quantum electrodynamics as a suitable method for computing the amplitude of a physical process, they rapidly became a fundamental mathematical object in quantum field theory. However, their abstract nature seems to suggest a wider usage, which actually exceeds the physical context. Indeed, as mathematical objects, they could simply be considered graphs that depict not only physical quantities but also biological or economic entities. We survey the analytical and algebraic properties of such diagrams to understand their utility in several areas of science, eventually providing some examples of recent applications. [ABSTRACT FROM AUTHOR]

Whole-brain connectome data characterize the connections among distributed neural populations as a set of edges in a large network, and neuroscience research aims to systematically investigate associations between brain connectome and clinical or experimental conditions as covariates. A covariate is often related to a number of edges connecting multiple brain areas in an organized structure. However, in practice, neither the covariate-related edges nor the structure is known. Therefore, the understanding of underlying neural mechanisms relies on statistical methods that are capable of simultaneously identifying covariate-related connections and recognizing their network topological structures. The task can be challenging because of false-positive noise and almost infinite possibilities of edges combining into subnetworks. To address these challenges, we propose a new statistical approach to handle multivariate edge variables as outcomes and output covariate-related subnetworks. We first study the graph properties of covariate-related subnetworks from a graph and combinatorics perspective and accordingly bridge the inference for individual connectome edges and covariate-related subnetworks. Next, we develop efficient algorithms to exact covariate-related subnetworks from the whole-brain connectome data with an |$\ell_0$| norm penalty. We validate the proposed methods based on an extensive simulation study, and we benchmark our performance against existing methods. Using our proposed method, we analyze two separate resting-state functional magnetic resonance imaging data sets for schizophrenia research and obtain highly replicable disease-related subnetworks. [ABSTRACT FROM AUTHOR]

Group Theory has diverse applications in mathematics and has been used to solve real-world problems, such as in cryptography, computer graphics, molecular systems biology, and crystal studies. In this article, we delve into a detailed analysis of subgroups of the free group of rank 2. The primary focus of this study is to develop an intuitive visualization for constructing a free set of generators for a free subgroup, using a graph-theoretic approach based on Stallings Foldings to provide a topological interpretation and solution to the problem. This algorithm leverages the connection between algebraic structures and geometric constructs, allowing for an intuitive understanding of the structure of a free group. An implementation of this algorithm is included in Python, making it immediately useful for computational applications. [ABSTRACT FROM AUTHOR]

Let ∑ni=0(-1)ilixn-i and ∑ni=0(-1)iqixn-i be the characteristic polynomials of the Laplacian matrix and signless Laplacian matrix of an n-vertex graph, respectively. Let αi = |qi - li|, 0 ≤ i ≤ n. In this paper, we find formulas for some of αi's. In particular, we compute αi's for some fullerene graphs. [ABSTRACT FROM AUTHOR]

In this paper, we calculate the expected values of the first and second Zagreb indices, denoted as E(M1) and E(M2) respectively, as well as the expected value of the forgotten index, E(F), for two models of random bipartite graphs. To evaluate our findings, we establish the growth rate by demonstrating that for a random bipartite graph G of order n in either model, the expected value of M1(G) is O(n³). Furthermore, we prove that the expected values of M2(G) and F(G) are both O(n4). [ABSTRACT FROM AUTHOR]

The second multiplicative Zagreb eccentricity index E*2 (G) of a simple connected graph G is expressed as the product of the weights ε(a)εG(b) over all edges ab of G, where ε(a) stands for the eccentricity of the vertex a in G. In this paper, some extremal problems on the E*2 index over some special graph classes including trees, unicyclic graphs and bicyclic graphs are examined, and the corresponding extremal graphs are characterized. Besides, the relationships between this vertex-eccentricity-based graph invariant and some well-known parameters of graphs and existing graph invariants such as the number of vertices, number of edges, minimum vertex degree, maximum vertex degree, eccentric connectivity index, connective eccentricity index, first multiplicative Zagreb eccentricity index and second multiplicative Zagreb index are investigated. [ABSTRACT FROM AUTHOR]

The design performance of real-time operating gas turbine power plants (GTPPs) deteriorates in terms of efficiency, reliability, and commercial availability due to aging, rubbing, contamination, and other similar problems. A manager minimizes operation and maintenance (O&M) expenses, consociating about the function of its basic structure (i.e., layout and design), availability (maintenance aspects), operation efficiency (trained workforce), safety and security, and other regulatory elements. Understanding plant structure improves performance, economical design, maintenance planning, etc. For a better understanding of design, a technique comprising graph theory, matrix method, and combinatorics is developed to determine the performance of GTPP. Detailed methodology for developing a system structure graph, various system structure matrices, and their permanent functions are described for the GTPP. For accessible and appropriate performance analysis, GTPP is divided into seven sub-systems. Structural interconnections between seven sub-systems of GTPP are as per real-time GTPP. The gas turbine system structure is developed in the form of a digraph. Matrix representation corresponding to digraph representation is developed, which is processed with the help of combinatorics. With the help of a computer programming tool developed in C++ for calculating the permanent of a matrix, the result comes out as a numerical value called the GTPP index. The methodology applied in the present work can be incorporated with standard computer programming tools developed for the performance assessment. In this way, it is easy to assess the dynamic behavior of the gas turbine system, as the methodology of the present work can incorporate tangible and intangible factors. Results obtained from the present methods agree with the available information in the literature. • The framework for exploring the dynamic behaviour of gas turbine systems is presented. • Graph theory, matrix method, and combinatorics are united into a single methodology. • Evaluations of efficiency, reliability, availability and maintainability are offered. • Recommendations for the ERAM evaluation of gas turbine systems are provided. [ABSTRACT FROM AUTHOR]

A set C of vertices in a graph G = (V, E) is an identifying code if it is dominating and any two vertices of V are dominated by distinct sets of codewords. This paper presents a survey of Iiro Honkala's contributions to the study of identifying codes with respect to several aspects: complexity of computing an identifying code, combinatorics in binary Hamming spaces, infinite grids, relationships between identifying codes and usual parameters in graphs, structural properties of graphs admitting identifying codes, and number of optimal identifying codes. [ABSTRACT FROM AUTHOR]

This paper formalizes the stepping stone problem introduced Ladoucer and Rebenstock [G] to the setting of simple graphs. This paper considers the set of functions from the vertices of our graph to N, which assign a fixed number of 1's to some vertices and assign higher numbers to other vertices by adding up their neighbors' assignments. The stepping stone solution is defined as an element obtained from the argmax of the maxima of these functions, and the maxima as its growth. This work is organized into work on the bounded and unbounded degree graph cases. In the bounded case, sufficient conditions are obtained for superlinear and sublinear stepping stone solution growth. Furthermore this paper demonstrates the existence of a basis of graphs which characterizes superlinear growth. In the unbounded case, properly sublinear and superlinear stepping stone solution growth are obtained. [ABSTRACT FROM AUTHOR]

Operations in the theory of graphs has a substantial inuence in the analytical and factual dimensions of the domain. In the realm of chemical graph theory, topological descriptor serves as a comprehensive graph invariant linked with a specific molecular structure. The study on the Sombor index is initiated recently by Ivan Gutman. The triangle parallel graph comprises of the edges of subdivision graph along with the edges of the original graph. In this paper, we make use of combinatorial inequalities related with the vertices, edges and the neighborhood concepts as well as the other topological descriptors in the computations for the determination of bounds of Sombor index for certain corona products involving the triangle parallel graph. [ABSTRACT FROM AUTHOR]

Abstract Background Identifying the molecular formula and fragmentation reactions of an unknown compound from its mass spectrum is crucial in areas such as natural product chemistry and metabolomics. We propose a method for identifying the correct candidate formula of an unidentified natural product from its mass spectrum. The method involves scoring the plausibility of parent candidate formulae based on a parent subformula graph (PSG), and two possible metrics relating to the number of edges in the PSG. This method is applicable to both electron-impact mass spectrometry (EI-MS) and tandem mass spectrometry (MS/MS) data. Additionally, this work introduces the two-dimensional fragmentation plot (2DFP) for visualizing PSGs. Results Our results suggest that incorporating information regarding the edges of the PSG results in enhanced performance in correctly identifying parent formulae, in comparison to the more well-accepted “MS/MS score”, on the 2016 Computational Assessment of Small Molecule Identification (CASMI 2016) data set (76.3 vs 58.9% correct formula identification) and the Research Centre for Toxic Compounds in the Environment (RECETOX) data set (66.2% vs 59.4% correct formula identification). In the extension of our method to identify the correct candidate formula from complex EI-MS data of semiochemicals, our method again performed better (correct formula appearing in the top 4 candidates in 20/23 vs 7/23 cases) than the MS/MS score, and enables the rapid identification of both the correct parent ion mass and the correct parent formula with minimal expert intervention. Conclusion Our method reliably identifies the correct parent formula even when the mass information is ambiguous. Furthermore, should parent formula identification be successful, the majority of associated fragment formulae can also be correctly identified. Our method can also identify the parent ion and its associated fragments in EI-MS spectra where the identity of the parent ion is unclear due to low quantities and overlapping compounds. Finally, our method does not inherently require empirical fitting of parameters or statistical learning, meaning it is easy to implement and extend upon. Scientific contribution Developed, implemented and tested new metrics for assessing plausibility of candidate molecular formulae obtained from HR-MS data.

Combinatorial algorithms such as those that arise in graph analysis, modeling of discrete systems, bioinformatics, and chemistry, are often hard to parallelize. The Combinatorial BLAS library implements key computational primitives for rapid development of combinatorial algorithms in distributed-memory systems. During the decade since its first introduction, the Combinatorial BLAS library has evolved and expanded significantly. This article details many of the key technical features of Combinatorial BLAS version 2.0, such as communication avoidance, hierarchical parallelism via in-node multithreading, accelerator support via GPU kernels, generalized semiring support, implementations of key data structures and functions, and scalable distributed I/O operations for human-readable files. Our article also presents several rules of thumb for choosing the right data structures and functions in Combinatorial BLAS 2.0, under various common application scenarios.

The Taxman game has proven to be hard to solve optimally, so efforts have been made to find heuristic strategies that do well in practice. We present results on the NP-hardness of a variant of the game via an equivalence to a particular kind of graph matching problem. Furthermore this equivalence is used to derive a winning strategy for all n along with efficiently computable lower and upper bounds on the optimal achievable score. [ABSTRACT FROM AUTHOR]

Background: Identifying the molecular formula and fragmentation reactions of an unknown compound from its mass spectrum is crucial in areas such as natural product chemistry and metabolomics. We propose a method for identifying the correct candidate formula of an unidentified natural product from its mass spectrum. The method involves scoring the plausibility of parent candidate formulae based on a parent subformula graph (PSG), and two possible metrics relating to the number of edges in the PSG. This method is applicable to both electron-impact mass spectrometry (EI-MS) and tandem mass spectrometry (MS/MS) data. Additionally, this work introduces the two-dimensional fragmentation plot (2DFP) for visualizing PSGs. Results: Our results suggest that incorporating information regarding the edges of the PSG results in enhanced performance in correctly identifying parent formulae, in comparison to the more well-accepted "MS/MS score", on the 2016 Computational Assessment of Small Molecule Identification (CASMI 2016) data set (76.3 vs 58.9% correct formula identification) and the Research Centre for Toxic Compounds in the Environment (RECETOX) data set (66.2% vs 59.4% correct formula identification). In the extension of our method to identify the correct candidate formula from complex EI-MS data of semiochemicals, our method again performed better (correct formula appearing in the top 4 candidates in 20/23 vs 7/23 cases) than the MS/MS score, and enables the rapid identification of both the correct parent ion mass and the correct parent formula with minimal expert intervention. Conclusion: Our method reliably identifies the correct parent formula even when the mass information is ambiguous. Furthermore, should parent formula identification be successful, the majority of associated fragment formulae can also be correctly identified. Our method can also identify the parent ion and its associated fragments in EI-MS spectra where the identity of the parent ion is unclear due to low quantities and overlapping compounds. Finally, our method does not inherently require empirical fitting of parameters or statistical learning, meaning it is easy to implement and extend upon. Scientific contribution: Developed, implemented and tested new metrics for assessing plausibility of candidate molecular formulae obtained from HR-MS data. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of normalized distance Laplacian matrices for signed graphs corresponding to the two signed distances defined for signed graphs. We characterize balance in signed graphs using these matrices and compare the normalized distance Laplacian spectral radius of signed graphs with that of all-negative signed graphs. Also we characterize the signed graphs having maximum normalized distance Laplacian spectral radius. [ABSTRACT FROM AUTHOR]

The multiplicative and additive compounds of a matrix play an important role in several fields of mathematics including geometry, multi-linear algebra, graph theory, combinatorics, and the analysis of nonlinear time-varying dynamical systems. There is a growing interest in applications of these compounds, and their generalizations, in systems and control theory. The goal of this tutorial paper is to provide a gentle and self-contained introduction to these topics with an emphasis on the geometric interpretation of the compounds, and to describe some of their recent applications including several non-trivial generalizations of positive systems, cooperative systems, contracting systems, and more. [ABSTRACT FROM AUTHOR]

Feynman diagrams represent one of the most powerful and fascinating tools developed in theoretical physics in the last century. Introduced within the framework of quantum electrodynamics as a suitable method for computing the amplitude of a physical process, they rapidly became a fundamental mathematical object in quantum field theory. However, their abstract nature seems to suggest a wider usage, which actually exceeds the physical context. Indeed, as mathematical objects, they could simply be considered graphs that depict not only physical quantities but also biological or economic entities. We survey the analytical and algebraic properties of such diagrams to understand their utility in several areas of science, eventually providing some examples of recent applications.

Graph theory and enumerative combinatorics are two branches of mathematical sciences that have developed astonishingly over the past one hundred years. It is especially important to point out that graph theory employs combinatorial techniques to solve key problems of characterization, construction, enumeration and classification of an enormous set of different families of graphs. This paper describes the construction of two classes of bigeodetic blocks using balanced incomplete block designs (BIBDs). On the other hand, even though graph theory and combinatorics have a close relationship, the opposite problem, that is, considering certain graph constructions when solving problems of combinatorics is not common, but possible. The construction of the second class of bigeodetic blocks described in this paper represents an example of how graph theory could somehow give a clue to the description of a problem of existence in combinatorics. We refer to the problem of existence for biplanes. A connection between the mentioned construction, the Bruck-Ryser-Chowla theorem and the problem of existence for biplanes is considered. [ABSTRACT FROM AUTHOR]

A cayley graph Cay(𝐺, 𝑆) of a group G, where S is the set of generators of G is a graph that has a vertex for each element of G and edge {g,gs} for g ∈ G and s ∈ s. In this work, we study the structural properties of undirected cayley graphs of the 𝛤1-non deranged permutation group (Gpr1) obtained from a modulo p function (for p = 5 and p is prime), and established that the generators of Gpr1 are not unique and also the undirected cayley graphs Cay(Gpr1, 𝑆) is not simple. [ABSTRACT FROM AUTHOR]

In this paper we initiate a systematic study of the Turán problem for edge-ordered graphs. A simple graph is called edge-ordered if its edges are linearly ordered. This notion allows us to study graphs (and in particular their maximum number of edges) when a subgraph is forbidden with a specific edge-order but the same underlying graph may appear with a different edge-order. We prove an Erdős-Stone-Simonovits-type theorem for edge-ordered graphs—we identify the relevant parameter for the Turán number of an edge-ordered graph and call it the order chromatic number. We establish several important properties of this parameter. We also study Turán numbers of edge-ordered paths, star forests and the cycle of length four. We make strong connections to Davenport-Schinzel theory, the theory of forbidden submatrices, and show an application in discrete geometry. [ABSTRACT FROM AUTHOR]

Fuzzy graphs and algorithms based on them can be very useful for the solution of many problems of practical interest. Since the uncertain and imprecise information is an essential characteristic feature virtually all real life problems, mostly uncertain, the modeling of such such problems using fuzzy graphs is difficult, even for an expert. A vague graph, an extension of the basic concept of a fuzzy graph, can be employed to deal with deeper aspects of uncertainty and imprecision for which the use of fuzzy graphs would not fully succeed. Domination is one of the most important issue in graph theory and has found many applications for the formulation and solution of many problems in various areas of science and technology exemplified by computer networks, artificial intelligence, combinatorial analyses, coding theory, etc. The concept of domination has been extended to fuzzy graphs, and vague graphs, to just name a few. We discuss here different concepts and properties related to domination in vague graphs such as an edge dominating set, an edge independent set, regular dominating set, regular independent set, and global dominating set, with some examples. Finally, we show an application of domination in vague graphs in the field of medicine that is related to the Influenza vaccine. [ABSTRACT FROM AUTHOR]

Hypertrees are high-dimensional counterparts of graph theoretic trees. They have attracted a great deal of attention by various investigators. Here we introduce and study hyperpaths—a particular class of hypertrees which are high dimensional analogs of paths in graph theory. A d-dimensional hyperpath is a d-dimensional hypertree in which every (d - 1) -dimensional face is contained in at most (d + 1) faces of dimension d. We introduce a possibly infinite family of hyperpaths for every dimension, and investigate its properties in greater depth for dimension d = 2 . [ABSTRACT FROM AUTHOR]

An H-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró et al. (Discrete Mathematics 100:267–279, 1992). An H-graph is proper if the representing subgraphs of H can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for S d -graphs and T-graphs, where S d is the star with d rays and T is an arbitrary fixed tree. Answering an open problem of Chaplick et al. (2016, personal communication), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of S d -graphs when parameterized by d, which involves the classical group-computing machinery by Furst et al. (in Proceedings of 11th southeastern conference on combinatorics, graph theory, and computing, congressum numerantium 3, 1980). We also show that the isomorphism problem of S d -graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of T-graphs when parameterized by the size of T. Lastly, we contribute an FPT-time combinatorial algorithm for isomorphism testing in the special case of proper S d - and T-graphs. [ABSTRACT FROM AUTHOR]

A graph is called equimatchable if all of its maximal matchings have the same size. Lesk et al. [Equi-matchable graphs, Graph Theory and Combinatorics (Academic Press, London, 1984) 239–254] has provided a characterization of equimatchable bipartite graphs. Motivated by the fact that this characterization is not structural, Frendrup et al. [A note on equimatchable graphs, Australas. J. Combin. 46 (2010) 185–190] has also provided a structural characterization for equimatchable graphs with girth at least five, in particular, a characterization for equimatchable bipartite graphs with girth at least six. In this paper, we extend the characterization of Frendrup by eliminating the girth condition. For an equimatchable graph, an edge is said to be a critical-edge if the graph obtained by the removal of this edge is not equimatchable. An equimatchable graph is called edge-critical, denoted by ECE, if every edge is critical. Noting that each ECE-graph can be obtained from some equimatchable graph by recursively removing non-critical edges, each equimatchable graph can also be constructed from some ECE-graph by joining some non-adjacent vertices. Our study reduces the characterization of equimatchable bipartite graphs to the characterization of bipartite ECE-graphs. [ABSTRACT FROM AUTHOR]

A cycle of a matroid is a disjoint union of circuits. A matroid is supereulerian if it contains a spanning cycle. To answer an open problem of Bauer in 1985, Catlin proved in [J. Graph Theory 12 (1988) 29–44] that for sufficiently large n $n$, every 2‐edge‐connected simple graph G $G$ with n=∣V(G)∣ $n=| V(G)| $ and minimum degree δ(G)≥n5 $\delta (G)\ge \frac{n}{5}$ is supereulerian. In [Eur. J. Combinatorics, 33 (2012), 1765–1776], it is shown that for any connected simple regular matroid M $M$, if every cocircuit D $D$ of M $M$ satisfies ∣D∣≥maxr(M)−55,6 $| D| \ge \max \left\{\frac{r(M)-5}{5},6\right\}$, then M $M$ is supereulerian. We prove the following. (i) Let M $M$ be a connected simple regular matroid. If every cocircuit D $D$ of M $M$ satisfies ∣D∣≥maxr(M)+110,9 $| D| \ge \max \left\{\frac{r(M)+1}{10},9\right\}$, then M $M$ is supereulerian. (ii) For any real number c $c$ with 0

Since the turn of the millennium the theory of random graphs has advanced by leaps and bounds. Random graphs have found very many applications, and many unexpected applications, in a remarkable variety of disciplines, and they are nowadays studied by mathematicians with various backgrounds (combinatorialists, probabilists, mathematical physicists), computer scientists and physicists. While this diversity has led to a proliferation of new models, questions and results, the community also has shattered, and by now different methods, terminologies and research agendas have come to coexist without much interaction. The workshop brought together distinct communities, who don't typically interact at their own intra-community events, but have each made significant contributions to the recent advancements in the theory. The workshop provided an effective platform for exchanging ideas, sharing insights, and building bridges across their respective domains. [ABSTRACT FROM AUTHOR]

This article announces the Combinatorics workshop organized by Peter Keevash, Wojciech Samotij and Benny Sudakov, which took place in early 2023. The workshop brought together experts from various areas of combinatorics to discuss recent developments, current themes and promising research directions.

Graph operations enable the modification and transformation of graphs, enhancing data representation as well as effectiveness in fields such as computer science, mathematics, and data analysis. Super line graph operations are a concept of advanced graph theory that is used in advanced mathematics and computer science. They are used to solve specific mathematical problems, especially in graph theory and Combinatorics. Topological numbers are numerical values connected with graph structures that are used to analyze structural characteristics and solve problems in fields such as chemistry and mathematics. They are important for simplifying complex data and enabling quantitative analysis. The general Randić number of some super line graph operations of number two with a three-diameter is investigated in this study. The pendant vertices are inserted without disturbing their diameter. Seven graphs of order five, each with a diameter of three, can be used to create twenty-three generalized super line graphs. [ABSTRACT FROM AUTHOR]

In the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1+∊)-approximation factor, the running time was recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1+∊)-approximation algorithm with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover, we obtain m1+o(1) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn) time is the mn0.9 + o(1)-time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary. In contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, ∊)-hop set introduced by Cohen [12] in the PRAM literature. An (h, ∊)-hop set of a graph G=(V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1+∊)-approximated by their h-hop distance (given by a path containing at most h edges) on G′=(V, E ∪ F). Our algorithm can maintain an (no(1), ∊)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools might be of independent interest. [ABSTRACT FROM AUTHOR]

We define a generalization of the classical secretary problem called the matroid secretary problem. In this problem, the elements of a matroid are presented to an online algorithm in uniformly random order. When an element arrives, the algorithm observes its value and must make an irrevocable decision whether or not to accept it. The accepted elements must form an independent set, and the objective is to maximize the combined value of these elements. We present an O(log k)-competitive algorithm for general matroids (where k is the rank of the matroid), and constant-competitive algorithms for several special cases including graphic matroids, truncated partition matroids, and bounded degree transversal matroids. We leave as an open question the existence of constant-competitive algorithms for general matroids. Our results have applications in welfare-maximizing online mechanism design for domains in which the sets of simultaneously satisfiable agents form a matroid. [ABSTRACT FROM AUTHOR]

In addition to binary self-dual codes, Vera was involved in the classification of self-dual codes over HT ht . In particular, under a specific inner product, the authors study the dual of HT ht -additive polycyclic codes. The largest possible minimum distance I d i of an HT ht even formally self-dual code satisfies HT ht . To construct a greedy code, fix an ordering of HT ht and a positive integer I d i . [Extracted from the article]

Enumerative Combinatorics focuses on the exact and asymptotic counting of combinatorial objects. It has fruitful connections to several disciplines, including statistical physics, algebraic combinatorics, probability theory, graph theory and computer science. This workshop brought together experts from all these various fields with the goal of promoting cooperation and interaction among researchers with largely varying backgrounds. It was the third workshop on this topic (the first two editions dating back to 2014 and 2018) and this time the main focus was on interactions with algebraic combinatorics. [ABSTRACT FROM AUTHOR]

Combinatorial expressions are obtained for the jump graph of the first and second Zagreb indices, the forgotten index, and their coindices, valid for any simple connected graph. [ABSTRACT FROM AUTHOR]

The text is a foreword for a special issue of the Journal of Information Science & Engineering on Combinatorial Mathematics and Computational Theory. It explains that these fields have a significant impact on computer science, mathematics, and science in general. Combinatorial Mathematics involves the study of discrete objects and has applications in various areas, while Computational Theory focuses on studying algorithms and their efficiency. The text also mentions a symposium that was held to promote academic exchanges and advance research in these fields. The special issue includes four papers on topics such as opinion optimization, local diagnosis, enumerating furthest pairs, and determining the 2-tuple total domination number of a graph. The authors express gratitude to the reviewers and authors for their contributions to the special issue. [Extracted from the article]