Search

We prove that, if m $m$ is sufficiently large, every graph on m+1 $m+1$ vertices that has a universal vertex and minimum degree at least ⌊2m3⌋ $\lfloor \phantom{\rule[-0.5em]{}{0ex}}\frac{2m}{3}\rfloor $ contains each tree T $T$ with m $m$ edges as a subgraph. Our result confirms, for large m $m$, an important special case of a conjecture by Havet, Reed, Stein, and Wood. The present paper builds on the results of a companion paper in which we proved the statement for all trees having a vertex that is adjacent to many leaves. [ABSTRACT FROM AUTHOR]

It is standard in chemistry to represent a sequence of reactions by a single overall reaction, often called a complex reaction in contrast to an elementary reaction. Photosynthesis $6 \text{CO}_2+6 \text{H}_2\text{O} \longrightarrow \text{C}_6\text{H}_{12}\text{O}_6 + 6 \text{O}_2$ is an example of such complex reaction. We introduce a mathematical operation that corresponds to summing two chemical reactions. Specifically, we define an associative and non-communicative operation on the product space ${\mathbb{N}}_0^n\times {\mathbb{N}}_0^n$ (representing the reactant and the product of a chemical reaction, respectively). The operation models the overall effect of two reactions happening in succession, one after the other. We study the algebraic properties of the operation and apply the results to stochastic reaction networks (RNs), in particular to reachability of states, and to reduction of RNs. [ABSTRACT FROM AUTHOR]

We consider profunctors between posets and introduce their graph and ascent. The profunctors Pro (P , Q) form themselves a poset, and we consider a partition I ⊔ F of this into a down-set I and up-set F , called a cut. To elements of F we associate their graphs, and to elements of I we associate their ascents. Our basic results is that this, suitably refined, preserves being a cut: We get a cut in the Boolean lattice of subsets of the underlying set of Q × P . Cuts in finite Booleans lattices correspond precisely to finite simplicial complexes. We apply this in commutative algebra where these give classes of Alexander dual square-free monomial ideals giving the full and natural generalized setting of isotonian ideals and letterplace ideals for posets. We study Pro (N , N) . Such profunctors identify as order preserving maps f : N → N ∪ { ∞ } . For our applications when P and Q are infinite, we also introduce a topology on Pro (P , Q) , in particular on profunctors Pro (N , N) . [ABSTRACT FROM AUTHOR]

Meaningful representation of large-scale non-Euclidean structured data, especially in complex domains like network security and IoT system, is one of the critical problems of contemporary machine learning and deep learning. Many successful cases of graph-based models and algorithms deal with non-Euclidean structured data. However, It is often undesirable to derive node representations by walking through the complete topology of a system or network (graph) when it has a very big or complicated structure. An important issue is using neighborhood knowledge to deduce the symmetric network's topology or graph. The traditional approach to solving the graph representation learning issue is surveyed from machine learning and deep learning perspectives. Second, include local neighborhood data encoded to the attention mechanism to define node solidarity and enhance node capture and interactions. The performance of the proposed model is then assessed for transduction and induction tasks that include downstream node categorization. The attention model taking clustering into account has successfully equaled or reached the state-of-the-art performance of several well-established node classification benchmarks and does not depend on previous knowledge of the complete network structure, according to experiments. Following a summary of the research, we discuss problems and difficulties that must be addressed for developing future graph signal processing algorithms and graph deep learning models, such as graph embeddings' interpretability and adversarial resilience. At the same time, it has a very positive impact on network security and artificial intelligence security. [ABSTRACT FROM AUTHOR]

In this paper, we used the permutation group together with the concept of cordiality in graph theory to introduce a new method of labeling. This construed permuted cordial labeling can be applied to all paths, cycles, fans and wheel graphs. Moreover, some other properties are investigated and show that the union of any two paths and the union of any two cycles are permuted cordial graphs. In addition, we investigated the permuted cordiality for the union of any path with cycle. [ABSTRACT FROM AUTHOR]

Biological networks are often large and complex, making it difficult to accurately identify the most important nodes. Node prioritization algorithms are used to identify the most influential nodes in a biological network by considering their relationships with other nodes. These algorithms can help us understand the functioning of the network and the role of individual nodes. We developed CentralityCosDist, an algorithm that ranks nodes based on a combination of centrality measures and seed nodes. We applied this and four other algorithms to protein–protein interactions and co-expression patterns in Arabidopsis thaliana using pathogen effector targets as seed nodes. The accuracy of the algorithms was evaluated through functional enrichment analysis of the top 10 nodes identified by each algorithm. Most enriched terms were similar across algorithms, except for DIAMOnD. CentralityCosDist identified more plant–pathogen interactions and related functions and pathways compared to the other algorithms. [ABSTRACT FROM AUTHOR]

Liver is an important metabolic organ in human body and is sensitive to toxic chemicals or drugs. Adverse reactions caused by drug hepatotoxicity will damage the liver and hepatotoxicity is the leading cause of removal of approved drugs from the market. Therefore, it is of great significance to identify liver toxicity as early as possible in the drug development process. In this study, we developed a predictive model for drug hepatotoxicity based on histopathological whole slide images (WSI) which are the by-product of drug experiments and have received little attention. To better represent the WSIs, we constructed a graph representation for each WSI by dividing it into small patches, taking sampled patches as nodes and calculating the correlation coefficients between node features as the edges of the graph structure. Then a WSI-level graph convolutional network (GCN) was built to effectively extract the node information of the graph and predict the toxicity. In addition, we introduced a gated attention global context vector (gaGCV) to combine the global context to make node features to contain more comprehensive information. The results validated on rat liver in vivo data from the Open TG-GATES show that the use of WSI for the prediction of toxicity is feasible and effective. • A graph convolutional network model is proposed to predict drug hepatotoxicity based on histopathological images. • A global context vector representing the entire graph information is developed based on the gated attention mechanism. • Two different relationship measures are used to compute the relationship between nodes to construct the edges of the graph. [ABSTRACT FROM AUTHOR]

In this work, we define ZG a topology on the vertex set of a graph G which preserves the connectivity of the graph, called Z-graphic topology. We prove that two isomorphic graphs have homeomorphic and symmetric Z-graphic topologies. We show that ZG is an Alexandroff topology and we give a necessary and sufficient condition for a topology to be Z-graphic. [ABSTRACT FROM AUTHOR]

The oriented chromatic number of a directed graph G is the minimum order of an oriented graph to which G has a homomorphism. The oriented chromatic number χ o (F) of a graph family F is the maximum oriented chromatic number over any orientation of any graph in F. For the family of hexagonal grids H 2 , Bielak (2006) proved that 5 ≤ χ o (H 2) ≤ 6. Here we close the gap by showing that χ o (H 2) ≥ 6. [ABSTRACT FROM AUTHOR]

The universal adjacency matrix U of a graph Γ, with adjacency matrix A, is a linear combination of A, the diagonal matrix D of vertex degrees, the identity matrix I, and the all-1 matrix J with real coefficients, that is, U = c 1 A + c 2 D + c 3 I + c 4 J , with c i ∈ R and c 1 ≠ 0. Thus, in particular cases, U may be the adjacency matrix, the Laplacian, the signless Laplacian, and the Seidel matrix. In this paper, we develop a method for determining the universal spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not). As an example, the method is applied to give an efficient algorithm to determine the characteristic polynomial of the Laplacian matrix of the symmetric squares of odd cycles, together with closed formulas for some of their eigenvalues. [ABSTRACT FROM AUTHOR]

An odd [ 1 , b ] -factor of a graph G is a spanning subgraph F of G with d F (x) ∈ { 1 , 3 , ⋯ , b } for every x ∈ V (G) , where b is a positive odd integer. Let | E (G) | be the size of G , and let ρ (G) be the spectral radius of G. In this article, we first verify three lower bounds for | E (G) | in a graph G of even order n to guarantee the existence of an odd [ 1 , b ] -factor in G. Then we prove two lower bounds for ρ (G) in a graph G of even order n to guarantee the existence of an odd [ 1 , b ] -factor in G. Furthermore, we create some extremal graphs to show all the lower bounds derived in this article are sharp. [ABSTRACT FROM AUTHOR]

Suppose G is a simple graph. If f is a mapping from V(G) ∪ E(G) to {1,2,...,k} such that f(e), f(u), f(v) are distinct for each edge e = uv of G, then f is called an E-total coloring of G using k colors (k-E-total coloring of G, in brief). For an E-total coloring f of a graph G and any vertex x of G, we denote the set {f(x)} ∪ {f(e)|e ∈ E(G) and e is incident with x} by C(x) and refer to it as the color set of x under f. If C(u) ≠ C(v) for any two different vertices u and v of V (G), then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. Let χvte(G) = {k|G has a VDET coloring using k colors }. Then the positive integer χvte(G) is called the VDET chromatic number of G. The VDET coloring of complete bipartite graph K5,n is discussed in this paper and the VDET chromatic number of K5,n has been obtained. [ABSTRACT FROM AUTHOR]

The characterizations of all graphs of order n with partition dimension 2; n - 2; n - 1 or n have been completely studied. Recently, all graphs of order n ≥ 11 and diameter two with partition dimension n-3 have been characterized. In this paper, we continue characterizing all graphs on n vertices with partition dimension n-3 and diameter either 3 or 4. This completes the characterization of all graphs of order n ≥ 11 with partition dimension n - 3. [ABSTRACT FROM AUTHOR]

Motivated by (random) lifetimes of electronic components or financial institutions we study the problem of maximizing the probability that (i) a random variable X is not smaller than another random object Y and (ii) that X and Y coincide within the class of all random variables X , Y with given univariate continuous distribution functions F and G , respectively. We show that the maximization problems correspond to finding copulas maximizing the mass of the endograph Γ ≤ (T) = { (x , y) ∈ [ 0 , 1 ] 2 : y ≤ T (x) } and the graph Γ (T) = { (x , T (x)) : x ∈ [ 0 , 1 ] } of T = G ∘ F − , respectively. After providing simple, copula-based proofs for the existence of copulas attaining the two maxima m ¯ T and w ¯ T we generalize the obtained results to the case of general (not necessarily monotonic) transformations T : [ 0 , 1 ] → [ 0 , 1 ] and derive simple and easily calculable formulas for m ¯ T and w ¯ T involving the distribution function F T of T (interpreted as random variable on [ 0 , 1 ]). The latter are then used to characterize all non-decreasing transformations T : [ 0 , 1 ] → [ 0 , 1 ] for which m ¯ T and w ¯ T coincide. A strongly consistent estimator for m ¯ T is derived and proven to be asymptotically normal under very mild regularity conditions. Several examples and graphics illustrate the main results and falsify some seemingly natural conjectures, an application of some of the obtained results to the seemingly unrelated topic of relative effects indicates the importance of the tackled questions. • Simple formulas for maximum/minimum prior/joint default probability are derived. • The situation of the two probabilities coinciding is characterized. • A strongly consistent estimator for the prior default probability is established. • The estimator is shown to be asymptotically normal. • An application to relative effects is given. [ABSTRACT FROM AUTHOR]

A graph G is a fractional $ (a,b,n) $ (a , b , n) -critical graph if removing any n vertices from G, the resulting subgraph still admits a fractional $ [a,b] $ [ a , b ] -factor. In this paper, we determine the exact tight isolated toughness bound for fractional $ (a,b,n) $ (a , b , n) -critical graphs. To be specific, a graph G is fractional $ (a,b,n) $ (a , b , n) -critical if $ \delta (G)\ge a+n $ δ (G) ≥ a + n and $ I(G)>a-1+\frac {n+1}{n_{a,b}} $ I (G) > a − 1 + n + 1 n a , b , where $ n_{a,b}\ge 2 $ n a , b ≥ 2 is an integer satisfies $ (n_{a,b}-1)a\le b\le n_{a,b}a-1 $ (n a , b − 1) a ≤ b ≤ n a , b a − 1. Furthermore, the sharpness of bounds is showcased by counterexamples. Our contribution improves a result from [W. Gao, W. Wang, and Y. Chen, Tight isolated toughness bound for fractional $ (k,n) $ (k , n) -critical graphs, Discrete Appl. Math. 322 (2022), 194–202] which established the tight isolated toughness bound for fractional $ (k,n) $ (k , n) -critical graphs. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a bipartite graph over the vertex set V = { 1 , ... , r } and let J = J (G) be the cover ideal of G in the polynomial ring R = K [ x 1 , ... , x r ]. It is known that there are integers b and t 0 such that reg J t = d (J) t + b is a linear function in t for all t ≥ t 0 . In this paper, we give effective bounds for b and t 0 . [ABSTRACT FROM AUTHOR]

Change detection (CD) is an important research topic in remote sensing, which has been applied in many fields. In the paper, we focus on the post-processing of difference images (DIs), i.e., how to further improve the quality of a DI after the initial DI is obtained. The importance of DIs for CD problems cannot be overstated, however few methods have been investigated so far for re-processing DIs after their acquisition. In order to improve the DI quality, we propose a global and local graph-based DI-enhancement method (GLGDE) specifically for CD problems; this is a plug-and-play method that can be applied to both homogeneous and heterogeneous CD. GLGDE first segments the multi-temporal images and DIs into superpixels with the same boundaries and then constructs two graphs for the DI with superpixels as vertices: one is the global feature graph that characterizes the association between the similarity relationships of connected vertices in the multi-temporal images and their changing states in a DI, the other is the local spatial graph that exploits the change information and contextual information of the DI. Based on these two graphs, a DI-enhancement model is built, which constrains the enhanced DI to be smooth on both graphs. Therefore, the proposed GLGDE can not only smooth the DI but also correct the it. By solving the minimization model, we can obtain an improved DI. The experimental results and comparisons on different CD tasks with six real datasets demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In the last few decades, studies of graph theory based on algebraic structures have been pursued. Many studies have inspected graphs via groups, rings, near-rings, and seminear-rings, and vice versa. In our study, first we introduce different type of υ-primary ideals (υ = 0, 1, 2, 3, c), which generalize υ-prime ideals (υ = 0, 1, 2, 3, c) in near-rings. Then, we provide some important characterizations of these newly initiated ideals. In addition, we explore some relationships among these ideals. Throughout, we furnish our results with appropriate examples. Finally, as an application, we provide characterizations of different graphs associated with these υ-primary ideals (υ = 0, 1, 2, 3, c) in near-rings. [ABSTRACT FROM AUTHOR]

We consider the spectral Neumann problem for the Laplace operator on a thin lattice comprised of nodes and ligaments. We pose the classical Pauling model on a one-dimensional graph which describes the multidimensional problem in the first approximation contains ordinary differential equations on its edges with Kirchhoff transmission conditions at its vertices. We construct two-term asymptotics for the spectral pairs {eigenvalue, eigenfunction} of the problem on the lattice. Basing on this analysis, we propound some refined asymptotic model on the graph with shortened edges that includes certain integral characteristics of the junction zones and actually accounts in the first approximation not only for the edge lengths but also for their arrangement, as well as for the shape and size of the nodes. [ABSTRACT FROM AUTHOR]

For a graph  G = (V , E)  and a function  f : V → { − 1 , + 1 } , if  S ⊆ V  then we write  f (S) = ∑ v ∈ S f (v) . A function  f  is said to be a non-zero vertex signed dominating function (for short, NVSDF) of  G  if  f (N [ v ]) = 0  holds for every vertex  v  in  G , and the non-zero vertex signed domination number of  G  is defined as  γ s b (G) = max { f (V) | f   is   an   NVSDF   of   G }.  In this paper, the novel concept of the non-zero vertex signed domination for graphs is introduced. There is also a special symmetry concept in graphs. Some upper bounds of the non-zero vertex signed domination number of a graph are given. The exact value of  γ s b (G)  for several special classes of graphs is determined. Finally, we pose some open problems. [ABSTRACT FROM AUTHOR]

In this paper, we introduce new kinds of graphs based on equality algebras. First of all, by using the meet operation we define the notion of zero divisors on equality algebra and study related properties. Then we introduce a meet graph on equality algebra by using zero divisors. In addition, we investigate some conditions for a meet graph to be a complete, connected and a star graph. Also, by using the notion of filters in equality algebras, we define an equivalence relation on equality algebras and then by using the equivalence classes we introduce two kinds of graphs on them. Finally, conditions for a graph based on these classes to be connected, or bipartite, or complete, or planar or an outer-planar graph are provided. [ABSTRACT FROM AUTHOR]

Graph attention networks stack self-attention layers to compute the neighbor-specific weights. Due to inherent noise and artificially correlated dimensions, attention scores fail to create optimal linear combinations for feature aggregation from the neighborhood. Multiple attention heads solve the problem to an extent but at the cost of additional memory overhead and larger variance in results. In this work, we introduce a novel concept of computing attention scores using a low-rank approximation of the intended neighborhood. The sub-space feature representation of the neighborhood discards the adverse effect of noise and artificially correlated dimensions. Extensive experiments on graph datasets show that the proposed framework outperforms the state-of-the-art methods. The reduced variance in our metrics Kruskal–Wallis test also indicates that the proposed model is able to give stable results as compared to other state-of-the-art methods. [ABSTRACT FROM AUTHOR]

A banknote is a currency issued by a country, and it was first introduced in the 16th century. The counterfeiting of banknotes by cunning criminals became a great challenge with the current advanced technology. Forensic scientists are using chemical methods, such as Fourier transform infrared (FTIR) spectroscopy for differentiating genuine and counterfeit banknotes. However, the FTIR spectra of banknotes may require further pattern recognition analysis due to their high similarities. In this paper, a fuzzy graph-based algorithm for authentication of the FTIR spectrum, namely chemometrics fuzzy autocatalytic set (c-FACS), is used to discriminate between genuine and counterfeit hundred Ringgit Malaysian (RM100) banknotes. The results show that the genuine and counterfeit RM100 banknotes have slightly distinct patterns when analyzed using c-FACS. In addition, the results are compared with RM50 banknotes, and the results reveal that the nodes or dominant axis varies between the two banknotes. To verify the reliability of the results, the results obtained via c-FACS are compared with principal component analysis (PCA). The c-FACS showed better performances as compared to PCA in terms of time consumption and observation. Thus, the c-FACS has the ability to assist forensic investigations involving banknote counterfeiting crimes. [ABSTRACT FROM AUTHOR]

In this paper, we study a graph whose vertices are the non-trivial conjugacy classes of a finite group, and two conjugacy classes C1 and C2 are adjacent if and only if we can find x ∈ C 1 and y ∈ C 2 such that x, y commute. In particular, we investigate groups whose corresponding graphs contain isolated vertices. We classify solvable groups with this property and show that if G is non-solvable, then either G / F (G) is almost simple or G is sharply 2-transitive. We determine almost simple groups with sporadic socles and some families of simple groups with this property. [ABSTRACT FROM AUTHOR]

The Agmon estimate shows that eigenfunctions of Schrödinger operators, - Δ ϕ + V ϕ = E ϕ , decay exponentially in the ‘classically forbidden’ region where the potential exceeds the energy level x : V (x) > E . Moreover, the size of | ϕ (x) | is bounded in terms of a weighted (Agmon) distance between x and the allowed region. We derive such a statement on graphs when - Δ is replaced by the graph Laplacian L = D - A : we identify an explicit Agmon metric and prove a pointwise decay estimate in terms of the Agmon distance. [ABSTRACT FROM AUTHOR]

• Grouping pixels reduced time and performance on edge detection and segmentation. • Expanding the analysis region yielded similar results with the original proposal. • The position of the features is important for the edge detection with random forest. • Sharp thick contours, uniform regions and small details impact the final segmentation. • Statistical analysis demonstrated superiority in segmentation over most edge maps. Gradient methods subject images to a series of operations to enhance some characteristics and facilitate image analysis, usually the contours of large objects. We argue that a gradient must show other characteristics, such as minor components and large uniform regions, particularly for the image segmentation task where subjective concepts such as region coherence and similarity are hard to interpret from the pixel information. This work extends the formalism of a previously proposed graph-based image gradient method that uses edge-weighted graphs aggregated with Random Forest (RF) to create descriptive gradients. We aim to explore more extensive input image areas and make changes driven by the RF mechanics. We evaluated the proposals on the edge and segmentation tasks, analyzing the gradient characteristics that most impacted the final segmentation. The experiments indicated that sharp thick contours are crucial, whereas fuzzy maps yielded the worst results even when created from deep methods with more precise edge maps. Also, we analyzed how uniform regions and small details impacted the final segmentation. Statistical analysis on the segmentation task demonstrated that the gradients created by the proposed are significantly better than most of the best edge maps methods and validated our original choices of attributes. [ABSTRACT FROM AUTHOR]

Peirce's beta graphs are roughly equivalent to our first-order predicate logic. However, Bellucci and Pietarinen have recently argued that the beta graphs are not well-equipped to handle asymmetric relative terms. I survey four proposed solutions to the problem and find them all wanting. I offer a fifth solution according to which Peirce's beta graphs function at three different levels of abstractness from natural language. I diagnose the problem of asymmetric relative terms as arising when we transition from the first to the second level of abstractness. Making grammatical information encoded in natural language explicit at the first level of abstractness and interpreting graphs at the second level of abstractness as shorn of grammatical information resolves the problem. The solution is both well-motivated by Peirce's own commitments and increases the expressiveness of the beta graphs. [ABSTRACT FROM AUTHOR]

In 2012 we announced "the House of Graphs" (https://houseofgraphs.org) (Brinkmann et al. 2013), which was a new database of graphs. The House of Graphs hosts complete lists of graphs of various graph classes, but its main feature is a searchable database of so called "interesting" graphs, which includes graphs that already occurred as extremal graphs or as counterexamples to conjectures. An important aspect of this database is that it can be extended by users of the website. Over the years, several new features and graph invariants were added to the House of Graphs and users uploaded many interesting graphs to the website. But as the development of the original House of Graphs website started in 2010, the underlying frameworks and technologies of the website became outdated. This is why we completely rebuilt the House of Graphs using modern frameworks to build a maintainable and expandable web application that is future-proof. On top of this, several new functionalities were added to improve the application and the user experience. This article describes the changes and new features of the new House of Graphs website. [ABSTRACT FROM AUTHOR]

• Open-source Python library for graph-based EEG modeling using connectivity measures. • Includes several connectivity measures, related to time and frequency domains. • Allows flexibility to define specific parameters related to the analysis of EEGs. • Output is provided in two formats: data structures and graph visual representation. • Promotes the use of EEGs as a clinical test for the study of connectivity patterns. Connectivity studies make it possible to identify alterations in brain connections and to associate these pathologies with different neurological disorders. However, a clinical test is necessary to obtain information about the state of the brain. Electroencephalograms (EEGs) provide this information in addition to being tests with other benefits for the patient (non-invasive, low-cost, high reproducibility). Graph theory can be used to represent both the anatomical and functional connections of the brain by means of connectivity measures. The procedure of transforming an EEG into a graph can be slightly tedious for researchers, especially when implementing different connectivity measures. The open-source Python library EEGraph automatically performs the modeling of an EEG through a graph, providing its matrix and visual representation. It recognizes various EEG input formats, identifying the number of electrodes and the location of each electrode in the brain. Moreover, it allows the user to choose from 12 connectivity measures to produce the graph from the EEG, with great flexibility to define specific parameters to adapt them to each study, including EEG time-windows segmentation and separation in frequency bands. The EEGraph library is developed as a tool, for researchers and clinical specialists in the field of neuroscience, that provides direct information on the connectivity of the brain from electroencephalography signals. Its documentation and source code are available at https://github.com/ufvceiec/EEGRAPH. It can be installed from the Python Package Index using pip install EEGRAPH. The EEGraph library was built aiming to facilitate the development of connectivity studies based on the modeling of electroencephalography tests through graphs. It includes a wide range of connectivity measures, which, together with the multiple output options, make EEGraph an easy to use and powerful tool with direct applications in both the clinical and neuroscience research fields. [ABSTRACT FROM AUTHOR]

Given a set R of robots, each one located at a different vertex of an infinite regular tessellation graph, we aim to explore the Arbitrary Pattern Formation (APF) problem. Given a multiset F of grid vertices such that | R | = | F | , APF asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translations, rotations, reflections. So far, as possible graph discretizing the Euclidean plane only the standard square grid has been considered in the context of the classical OBLOT model. However, it is natural to consider also the other regular tessellation graphs, that are triangular and hexagonal grids. In particular, the former can be considered as the most general in terms of possible symmetries and trajectories. We provide a resolution algorithm for APF when the initial configuration is asymmetric and the considered topology is any regular tessellation graph. The algorithm and its correctness are based on a rigorous methodology. • We solve the Arbitrary Pattern Formation problem for asynchronous robots moving on triangular grids. • We show that the provided algorithm works also for square and hexagonal grids. • The algorithm is able to create patterns with possible multiplicities. • The algorithm and its correctness are based on a rigorous methodology. [ABSTRACT FROM AUTHOR]

Due to the development of sequencing technology and the great reduction in sequencing costs, an increasing number of plant genomes have been assembled, and numerous genomes have revealed large amounts of variations. However, a single reference genome does not allow the exploration of species diversity, and therefore the concept of pan-genome was developed. A pan-genome is a collection of all sequences available for a species, including a large number of consensus sequences, large structural variations, and small variations including single nucleotide polymorphisms and insertions/deletions. A simple linear pan-genome does not allow these structural variations to be intuitively characterized, so graph-based pan-genomes have been developed. These pan-genomes store sequence and structural variation information in the form of nodes and paths to store and display species variation information in a more intuitive manner. The key role of graph-based pan-genomes is to expand the coordinate system of the linear reference genome to accommodate more regions of genetic diversity. Here, we review the origin and development of graph-based pan-genomes, explore their application in plant research, and further highlight the application of graph-based pan-genomes for future plant breeding. [ABSTRACT FROM AUTHOR]

Recently, Asao and Izumihara introduced CW-complexes whose homology groups are isomorphic to direct summands of the graph magnitude homology group. In this paper, we study the homotopy type of the CW-complexes in connection with the diagonality of magnitude homology groups. We prove that the Asao–Izumihara complex is homotopy equivalent to a wedge of spheres for pawful graphs introduced by Y. Gu. The result can be considered as a homotopy type version of Gu’s result. We also formulate a slight generalization of the notion of pawful graphs and find new non-pawful diagonal graphs of diameter 2. [ABSTRACT FROM AUTHOR]

Gain graphs are graphs where the edges are given some orientation and labeled with the elements (called gains) from a group so that the gains are inverted when we reverse the direction of the edges. Generalizing the notion of gain graphs, skew gain graphs have the property that the gain of a reversed edge is the image of edge gain under an anti-involution. In this paper, we deal with the adjacency matrix of skew gain graphs with an involutive automorphism on a field of characteristic zero and their characteristic polynomials. Spectra of some particular skew gain graphs are also discussed. [ABSTRACT FROM AUTHOR]

Urban density is central to urban research and planning and can be defined in numerous ways. Most measures of urban density however are biased by arbitrary chosen spatial units at their denominator and ignore the relative location of elementary urban objects within those units. We solve these two problems by proposing a new graph-based density index which we apply to the case of buildings in Belgium. The method includes two main steps. First, a graph-based spatial descending hierarchical clustering (SDHC) delineates clusters of buildings with homogeneous inter-building distances. A Moran scatterplot and a maximum Cook's distance are used to prune the minimum spanning tree at each iteration of the SDHC. Second, within each cluster, the ratio of the number of buildings to the sum of inter-building distances is calculated. This density of buildings is thus defined independently of the definition of any basic spatial unit and preserves the built-up topology, i.e. the relative position of buildings. The method is parsimonious in parameters and can easily be transferred to other punctual objects or extended to account for additional attributes. [ABSTRACT FROM AUTHOR]

A path factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices. We write P≥k = {Pi : i ≥ k}. Then a P≥k-factor of G means a path factor in which every component admits at least k vertices, where k ≥ 2 is an integer. A graph G is called a P≥k-factor avoidable graph if for any e ∈ E(G), G admits a P≥k-factor excluding e. A graph G is called a (P≥k, n)-factor critical avoidable graph if for any Q ⊆ V (G) with |Q| = n, G − Q is a P ≥k-factor avoidable graph. Let G be an (n + 2)-connected graph. In this paper, we demonstrate that (i) G is a (P≥2, n)-factor critical avoidable graph if t o u g h (G) > n + 2 4 ; (ii) G is a (P≥3, n)-factor critical avoidable graph if t o u g h (G) > n + 1 2 ; (iii) G is a (P≥2, n)-factor critical avoidable graph if I (G) > n + 2 3 ; (iv) G is a (P≥3, n)-factor critical avoidable graph if I (G) > n + 3 2 . Furthermore, we claim that these conditions are sharp. [ABSTRACT FROM AUTHOR]

In This paper, we study the relationships between graphs and the prime spectrum of unitary commutative rings. It is shown that a graph G equipped with the G-right topology satisfies some spectral properties. In particular we give a necessarily and sufficient condition to obtain a spectral graph. [ABSTRACT FROM AUTHOR]

The main aim of the paper is to give the crossing number of the join product G * + D n . The connected graph G * of order six is isomorphic to K 3 , 3 \ e obtained by removing one edge from the complete bipartite graph K 3 , 3 , and the discrete graph D n consists of n isolated vertices. The proofs were carried out with the help of several possible redrawings of the graph G * with respect to its many symmetries. [ABSTRACT FROM AUTHOR]

Abstract compositional spaces have long been used to illustrate structural relationships within and between musical works. However, despite robust scholarship employing spaces to depict the possibilities available to composers, space-based analytical methods have rarely been used to study the performance of music. Through case studies drawn from improvised and notated music, this article introduces the questions and methodologies by which analogous spaces for performance, which the author terms performance spaces, may be generated and analyzed. The author also considers the unique properties of hybrid spaces that combine the tools of discrete mathematics, such as graphs, with distance-based metrics. [ABSTRACT FROM AUTHOR]

The Owen graph value for games with coalition structure and graph restricted communication was introduced by Vázquez-Brage et al. (Games Econ Behav 12: 42–53, 1996). It has been known that the value satisfies the axiom of component efficiency, requiring that the players of a component share the benefits generated by this component among themselves. In this paper we extend the Owen graph value to an efficient value and we provide axiomatic characterizations of this value. [ABSTRACT FROM AUTHOR]

A graph G is said to be fractional (a , b , k) -critical covered if for any W ⊆ V (G) with | W | = k , G − W is fractional [ a , b ] -covered. In this article, we demonstrate that a graph G of order n is fractional (a , b , k) -critical covered if G satisfies δ (G) ≥ (t − 1) (a + 1) + k , n ≥ (a + b) (t (a + b) − 2) + b k + 2 b , and | N G (x 1) ∪ N G (x 2) ∪ ⋯ ∪ N G (x t) | ≥ a n + b k + 2 a + b for any independent subset { x 1 , x 2 , ... , x t } of G , which is an improvement and extension of Yuan and Hao's previous result (Yuan and Hao, 2020). [ABSTRACT FROM AUTHOR]

It was shown in 2006 that among the nonsingular trees T (whose adjacency matrix A(T) is nonsingular), the corona trees (trees that are obtained by taking any tree T and then adding a new pendant vertex at each vertex of T) are the only ones which satisfy the reciprocal eigenvalue property (λ is an eigenvalue of A(T) if and only if 1 λ is an eigenvalue of A(T), where their multiplicities are allowed to be different). A general question remained open. Can there be a tree which has at least one zero eigenvalue and whose nonzero eigenvalues satisfy the reciprocal eigenvalue property? In this note, we show that there are no such trees with at least two vertices. The proof is a beautiful application of the product of graphs. [ABSTRACT FROM AUTHOR]

We develop a general spectral framework to analyze quantum fractional revival in quantum spin networks. In particular, we determine when the adjacency algebra of a graph contains a matrix of a block diagonal form required for fractional revival, and introduce generalizations of the notions of cospectral and strongly cospectral vertices to arbitrary subsets of vertices. We give several constructions of graphs admitting fractional revival. This work resolves two open questions of Chan et al. (2019) [6]. [ABSTRACT FROM AUTHOR]

Isolated toughness of graph G is formulated by minimizing the ratio | S | / i (G − S) over all S ⊆ V (G) with i (G − S) ≥ 2 , where i (G − S) is the number of isolated vertices after removing vertex subset S from G. The previous works reveal that there exist explicit correlations between isolated toughness and fractional critical graphs (a.k.a. the graph admits a fractional factor after deleting given number of vertices). However, among the existing isolated toughness bounds, the term with respect to n (the number of removed vertices) is always at least n. In this paper, the exactly sharp isolated toughness bound for fractional (k , n) -critical graph is determined which reveals that the coefficient of term with regard to n can be reduced to 1/2. It is well acknowledged that some tight toughness related bounds can reach to the extreme value, while others cannot. We give an explanation why these tight bounds in various settings possess such pattern differences. [ABSTRACT FROM AUTHOR]

Canonical decompositions, such as the Gallai–Edmonds and Dulmage–Mendelsohn decompositions, are a series of structure theorems that form the foundation of matching theory. The classical Kotzig–Lovász decomposition is a canonical decomposition applicable to a special class of graphs with perfect matchings, called factor-connected graphs, and is famous for its contribution to the studies of perfect matching polytopes and lattices. Recently, this decomposition has been generalized for general graphs with perfect matchings; this generalized decomposition is called the general Kotzig–Lovász decomposition. In fact, this generalized decomposition can be presented as a component of a more composite canonical decomposition called the Basilica decomposition. As such, the general Kotzig–Lovász decomposition has contributed to the derivation of various new results in matching theory, such as an alternative proof of the tight cut lemma and a characterization of maximal barriers in general graphs. Joins in grafts, also known as T -joins in graphs, is a classical concept in combinatorics and is a generalization of perfect matchings in terms of parity. More precisely, minimum joins and grafts are generalizations of perfect matchings and graphs with perfect matchings, respectively. Under the analogy between matchings and joins, analogues of the canonical decompositions for grafts are expected to be strong and fundamental tools for studying joins. In this paper, we provide a generalization of the general Kotzig–Lovász decomposition for arbitrary grafts. Our result also contains Sebö's generalization of the classical Kotzig–Lovász decomposition for factor-connected grafts. From our results in this paper, a generalization of the Dulmage–Mendelsohn decomposition, which is originally a classical canonical decomposition for bipartite graphs, has been obtained for bipartite grafts. This paper is the first of a series of papers that establish a generalization of the Basilica decomposition for grafts. [ABSTRACT FROM AUTHOR]

The linear arboricity l a (G) of a graph G is the minimum number of linear forests which partition the edges of G. In 1980, Akiyama et al. conjectured that for any graph G , ⌈ Δ (G) 2 ⌉ ≤ l a (G) ≤ ⌈ Δ (G) + 1 2 ⌉. In the paper, we establish two essential structural properties of K 5 -minor free graphs G , one is used to confirm the conjecture for all K 5 -minor free graphs, the other is devoted to proving that l a (G) = ⌈ Δ (G) 2 ⌉ holds if Δ (G) ≥ 9. In addition, we prove here that if G is a K 5 − -minor free graph and Δ (G) ≥ 5 , then l a (G) = ⌈ Δ (G) 2 ⌉. [ABSTRACT FROM AUTHOR]

Since support vector machine (SVM) considers all the training samples equally, it suffers from the problems of noise/outliers and class imbalance. Although many fuzzy support vector machines (FSVMs) have been proposed to suppress the effect of noise/outliers and class imbalance, most of them ignore the impact of the curse of dimensionality on the discriminative performance of fuzzy membership function and do not give the fuzzy membership function corresponding to the kernel space, which seriously reduces the performance of FSVM. To solve these problems, we propose the fuzzy support vector machine with graph (GraphFSVM) in this paper. Specifically, we first design a graph-based fuzzy membership function to accurately assess the importance of samples in original feature space and prove that the function can mine discriminative information between samples in high-dimensional data. Additionally, since the data distribution in kernel space is different from those in the original feature space, a method is provided to calculate the fuzzy membership function in the kernel space. Finally, the GraphFSVM model analyzes samples of each class independently, this suppresses the effect of class imbalance. Following the above principles, we design the graph-based fuzzy support vector machine and propose a detailed optimization method. Experimental results on UCI, gene expression, and image datasets show that the GraphFSVM has better generalization and robustness than other state-of-the-art methods. [ABSTRACT FROM AUTHOR]

We investigate properties of sparse and tight surface graphs. In particular we derive topological inductive constructions for (2 , 2) -tight surface graphs in the case of the sphere, the plane, the twice punctured sphere and the torus. In the case of the torus we identify all 116 irreducible base graphs and provide a geometric application involving contact graphs of configurations of circular arcs. [ABSTRACT FROM AUTHOR]

Fuzzy topological topographic mapping ( F T T M ) is a mathematical model that consists of a set of homeomorphic topological spaces designed to solve the neuro magnetic inverse problem. The key to the model is its topological structure that can accommodate electrical or magnetic recorded brain signal. A sequence of FTTM, F T T M n , is an extension of FTTM whereby its form can be arranged in a symmetrical form, i.e., polygon. The special characteristic of F T T M , namely, the homeomorphisms between its components, allows the generation of new F T T M . The generated F T T M s can be represented as pseudo graphs. A pseudo-graph consists of vertices that signify the generated F T T M and edges that connect their incidence components. A graph of pseudo degree zero, G 0 (F T T M n k  ) , however, is a special type of graph where each of the F T T M components differs from its adjacent. A researcher posted a conjecture on G 0 3 (F T T M n 3) in 2014, and it was finally proven in 2021 by researchers who used their novel grid-based method. In this paper, the extended G 0 3 (F T T M n 3) , namely, the conjecture on G 0 4 (F T T M n 4) that was posed in 2018, is narrated and proven using simple mathematical induction. [ABSTRACT FROM AUTHOR]

A new synthesis methodology, which offers design harmony of multiple analog filter and oscillator topologies is presented. Vertices of a bipartite graph are defined with simple mathematical function, denoted as cell. Weight of the edges are denoted by relation operator. A general theory has been developed based on graph and a set of traversal rules conjugated with cell, to produce multiple number of second-order function (SOF) in terms of cells. Theoretical approach has been facilitated with operational transconductance amplifier (OTA)-based circuit realization of multiple filter and oscillator topologies, and abridged with algorithm, which may lead to virtual EDA tool and field programmable analog array (FPAA). The proposed synthesis approach is validated with SPICE simulation. [ABSTRACT FROM AUTHOR]

In this study, n-point graphs and n-point texture spaces are examined and graphs that we will call Texture Graphs are obtained. In addition, it is shown how a ditopology can be obtained on the given texture space with the help of this graph. It is shown that a di-topological texture space (S,SΚ,Τ) associated with di-graph (S, G) and each di-graph (S, G) with n points associated with a unique ditopology on texture space. With the graph obtained from co-topology, it has been seen that there is alternative information for the solution of many mathematical and non-mathematical problems in terms of application. [ABSTRACT FROM AUTHOR]