Search

Assume there exists a function h : E (G) → [ 0 , 1 ] such that g (x) ≤ ∑ e ∈ E (G) , x ∋ e h (e) ≤ f (x) for every vertex x of G. The spanning subgraph of G induced by the set of edges { e ∈ E (G) : h (e) > 0 } is called a fractional (g , f) -factor of G with indicator function h. Let M and N be two disjoint sets of independent edges of G satisfying | M | = m and | N | = n. We say that G possesses a fractional (g , f) -factor with the property E (m , n) if G contains a fractional (g , f) -factor with indicator function h such that h (e) = 1 for each e ∈ M and h (e) = 0 for each e ∈ N. In this article, we discuss stability number and minimum degree conditions for graphs to possess fractional (g , f) -factors with the property E (1 , n). Furthermore, we explain that the stability number and minimum degree conditions declared in the main result are sharp. [ABSTRACT FROM AUTHOR]

The collection of SuperDARN ionospheric echo data to make ionospheric convection maps is of great significance for Space Weather research. The ionospheric echoes for SuperDARN are generally mixed with scatter from the ground or sea surface, thus the clustering analysis of SuperDARN backscatter echoes is important. In this paper, the first implementation of deep clustering based on the graph automatic encoder network is efficiently realized for classifying the SuperDARN data. In addition, the model is compared with the traditional algorithm and machine learning clustering algorithms. Application of the model to sample data reveals that the deep clustering algorithm can capture the structural characteristics of the echoes and improve the accuracy of echo clustering and classifying. [ABSTRACT FROM AUTHOR]

A spanning k -tree of a connected graph G is a spanning tree in which each vertex admits degree at most k. It is easy to see that a spanning 2-tree is a Hamiltonian path. Hence, a spanning k -tree is an extended concept of a Hamiltonian path. Let Q (G) denote the distance signless Laplacian matrix of a graph G. The largest eigenvalue η 1 (G) of Q (G) is called the distance signless Laplacian spectral radius of G. Liu and Li characterized a connected graph with a perfect matching with respect to the distance signless Laplacian spectral radius (Liu and Li, 2021). Win characterized a connected graph with a spanning k -tree via the number of connected components (Win, 1989). Motivated by Liu and Li's and Win's results, in this paper we investigate the relations between the spanning k -tree and the distance signless Laplacian spectral radius in a connected graph and prove an upper bound for η 1 (G) in a connected graph G to guarantee the existence of a spanning k -tree. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. A set S ⊆ V is a total restrained dominating set if every vertex is adjacent to a vertex in S , and every vertex in V − S is adjacent to a vertex in V − S. The total restrained domination number of G , denoted γ t r (G) , is the smallest cardinality of a total restrained dominating set of G. In this paper we show that if G is a K 1 , ℓ -free graph with δ ≥ ℓ ≥ 3 and δ ≥ 5 , then γ t r (G) ≤ n 1 − (2 δ − 3) (2 δ) δ δ − 1 + o δ (1) . [ABSTRACT FROM AUTHOR]

Diagnosability is a fundamental consideration when designing an interconnected network. The PMC and MM ∗ fault diagnosis models are the two most commonly used models. Both the g -good-neighbour diagnosability and g -extra diagnosability of an interconnection network have been two of the hot topics in the intersectional research areas of Graph theory and Computer Science, which become increasingly attractive for new solutions to real-world problems. However, there are still some problems in the transformation from the concepts of Computer Science to that of mathematics. In this paper, we systematically study such problems and give a strict proof from concepts to mathematical conclusions. In the terms of results, we not only give the relationship between g -good-neighbour diagnosabilities of the network under PMC model and MM ∗ model, but also between g -extra diagnosabilities of the network under PMC and MM ∗ models. To apply our results, we give an application on the enhanced hypercube in the end and derive a lemma explaining whether these are 3-cycles in enhanced hypercubes and how many common neighbours for two vertices of enhanced hypercubes under different values of k in the meantime. [ABSTRACT FROM AUTHOR]

A mobile agent, which is an autonomous device navigating in a graph, has to explore a given graph by visiting all of its nodes. We adopt the (arguably) weakest possible model of such a device: a deterministic memoryless automaton (DMA), i.e., a deterministic automaton with a single state. As expected, such a weak machine is incapable of exploring many graphs without marking nodes. Hence we allow the agent to use identical movable pebbles that can be dropped on nodes or picked from them. It turns out that this marking capability significantly enhances the exploration power of the agent. Our goal is to study how the availability of pebbles impacts the class of graphs that a DMA can explore. We first concentrate on finite graphs and show that any finite tree can be explored by a DMA without pebbles but there exist (small) finite graphs that cannot be explored by a DMA without pebbles. Then we turn attention to infinite graphs and fully characterize the class of infinite trees that can be explored by a DMA without pebbles. We also define a large class of infinite trees that can be explored by a DMA with finitely many pebbles. It turns out that many of these trees cannot be explored by a DMA without pebbles. On the other hand, we show a large class of infinite trees that cannot be explored by a DMA with finitely many pebbles. Thus, availability of pebbles yields a strict hierarchy of difficulty of exploration of infinite graphs by a DMA, and this hierarchy is strict even for the class of infinite trees: some trees can be explored without pebbles, some trees can be explored with finitely many pebbles but not without pebbles, and some trees require infinitely many pebbles. Finally, we consider exploration by a DMA with infinitely many pebbles. It turns out that all infinite trees can be explored by a DMA with infinitely many pebbles. By contrast, we construct infinite graphs that cannot be explored by any DMA, even with infinitely many pebbles. [ABSTRACT FROM AUTHOR]

An isolating set in a graph is a set X of vertices such that every edge of the graph is incident with a vertex of X or its neighborhood. The isolation number of a graph, or equivalently the vertex-edge domination number, is the minimum number of vertices in an isolating set. Caro and Hansberg, and independently Żyliński, showed that the isolation number is at most one-third the order for every connected graph of order at least 6. We show that in fact all such graphs have three disjoint isolating sets. Further, using a family introduced by Lemańska, Mora, and Souto-Salorio, we determine all graphs with equality in the original bound. [ABSTRACT FROM AUTHOR]

Given a pair of real symmetric matrices A , B ∈ R n × n with nonzero patterns determined by the edges of any pair of chosen graphs on n vertices, we consider an inverse eigenvalue problem for the structured matrix C = [ A B I O ] ∈ R 2 n × 2 n. We conjecture that C can attain any spectrum that is closed under conjugation. We use a structured Jacobian method to prove this conjecture for A and B of orders at most 4 or when the graph of A has a Hamilton path, and prove a weaker version of this conjecture for any pair of graphs with a restriction on the multiplicities of eigenvalues of C. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and A (G) be the adjacency matrix of G. A diagonal matrix with diagonal entries ±1 is called a signature matrix. If A (G) is nonsingular and X = S A (G) − 1 S − 1 is entrywise nonnegative for some signature matrix S , then X can be viewed as the adjacency matrix of a unique weighted graph. It is called the inverse of G , denoted by G +. A graph G is said to have the reciprocal eigenvalue property (property(R)) if A (G) is nonsingular, and 1 λ is an eigenvalue of A (G) whenever λ is an eigenvalue of A (G). Further, if λ and 1 λ have the same multiplicity for each eigenvalue λ , then G is said to have the strong reciprocal eigenvalue property (property (SR)). It is known that for a tree T , the following conditions are equivalent: a) T + is isomorphic to T , b) T has property (R), c) T has property (SR) and d) T is a corona tree (it is a tree which is obtained from another tree by adding a new pendant at each vertex). Studies on the inverses, property (R) and property (SR) of bipartite graphs are available in the literature. However, their studies for the non-bipartite graphs are rarely done. In this article, we study the inverse and property (SR) for non-bipartite graphs. We first introduce an operation, which helps us to study the inverses of non-bipartite graphs. As a consequence, we supply a class of non-bipartite graphs for which the inverse graph G + exists and G + is isomorphic to G. It follows that each graph G in this class has property (SR). [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]

We develop a new approach to recurrence and the existence of non-constant harmonic functions on infinite weighted graphs. The approach is based on the capacity of subsets of metric boundaries with respect to intrinsic metrics. The main tool is a connection between polar sets in such boundaries and null sets of paths. This connection relies on suitably diverging functions of finite energy. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a finite, combinatorial graph. We define a notion of curvature on the vertex set V via the inverse of the resistance distance matrix. We prove that this notion of curvature has a number of desirable properties. Graphs with curvature bounded from below by K > 0 have diameter bounded from above. The Laplacian L = D − A satisfies a Lichnerowicz estimate, there is a spectral gap λ 2 ≥ 2 K. We obtain matching two-sided bounds on the maximal commute time between any two vertices in terms of | E | ⋅ | V | − 1 ⋅ K − 1 . Moreover, we derive quantitative rates for the mixing time of the corresponding Markov chain and prove a general equilibrium result. [ABSTRACT FROM AUTHOR]

The toughness of a graph G is defined to be the minimum value of | S | / k (G − S) , where k (G − S) denotes the number of components of G − S and the minimum is taken over all cut-sets S ⊆ V (G). In this paper we propose a version for weighted graphs that depends on the weights in both S and G − S. Apart from considering bounds and basic properties, our focus is on the problem of assigning weights so as to maximize the parameter. [ABSTRACT FROM AUTHOR]

Let G be a (simple) graph on n ≥ 3 vertices and (d 1 , ... , d n) be the degree sequence of G with d 1 ≤ ⋯ ≤ d n . The classical Chvátal's theorem states that if d m ≥ m + 1 or d n − m ≥ n − m for each m with 1 ≤ m < n 2 (called the Chvátal-condition), then G is hamiltonian. Similarly, let G be a (simple) balanced bipartite graph on n ≥ 4 vertices and (d 1 , ... , d n) be the degree sequence of G with d 1 ≤ ⋯ ≤ d n . The classical Chvátal's theorem states that if d m ≥ m + 1 or d n 2 ≥ n 2 − m + 1 for each m with 1 ≤ m ≤ n 4 (called the Chvátal-condition), then G is hamiltonian. In this paper, for an abelian group A of order at least 4, we show that if a graph G satisfies the Chvátal-condition, then G is A -connected if and only if G ≠ C 4 , where C ℓ is a cycle of length ℓ. Moreover, for an abelian group A of order at least 5, we also show that if a balanced bipartite graph G satisfies the Chvátal-condition, then G is A -connected if and only if G ≠ C 6 . [ABSTRACT FROM AUTHOR]

We provide three infinite families of graphs in the Johnson and Grassmann schemes that are not uniquely determined by their spectrum. We do so by constructing graphs that are cospectral but non-isomorphic to these graphs. [ABSTRACT FROM AUTHOR]

Logical reasoning of context is vital for reading comprehension, which requires to explore the logical relationship through sentence structure. However, previous methods of logical symbols and graph-based models do not make full explore the relationships among entities. In this paper, we present a verb-driven dual-graph network (VDGN) that utilizes core verbs of sentences to model the inter-sentence relationship by the ability of verbs to express linguistic context and the shortest dependency path to model the relationship between entities of intra-sentence. We construct a context graph and a query graph respectively through the above method. In order to predict the answer correctly, our framework fuses information from the context graph and the query graph applying a bi-directional attention mechanism on graph data. We evaluate our approach on two public logical reasoning machine reading comprehension(MRC) datasets: ReClor and LogiQA. Experiments on representative benchmark datasets demonstrate the effectiveness of our approach. • Verbs and dependency parser can solve logical reasoning problems in text. • Verbs can express linguistic context and the logical relationship between entities. • Graph-based and bi-directional attention can enhance the model's text comprehension. [ABSTRACT FROM AUTHOR]

An integer k -matching of a graph G is a function h : E (G) → { 0 , 1 , ... , k } such that ∑ e ∈ Γ (v) h (e) ≤ k for any v ∈ V (G) , where Γ (v) is the set of edges incident to v. The integer k -matching number of G , denoted by m k (G) , is the maximum number of ∑ e ∈ E (G) h (e) over all integer k -matching h of G. In this paper, we establish the following lower bounds on the sum of the integer k -matching number of a graph G and its complement by using Gallai–Edmonds Structure Theorem: (1) m k (G) + m k (G ¯) ≥ ⌊ n k 2 ⌋ for n ≥ 2 ; (2) if G and G ¯ are non-empty, then for n ≥ 25 , m k (G) + m k (G ¯) ≥ ⌊ n k + k 2 ⌋ ; (3) if G and G ¯ have no isolated vertices, then for n ≥ 25 , m k (G) + m k (G ¯) ≥ ⌊ n k 2 ⌋ + 2 k. Furthermore, all extremal graphs attaining the lower bounds are also characterized. [ABSTRACT FROM AUTHOR]

In this paper, we take a modest first step towards a systematic study of chromatic numbers of Cayley graphs on abelian groups. We lose little when we consider these graphs only when they are connected and of finite degree. As in the work of Heuberger and others, in such cases the graph can be represented by an m × r integer matrix, where we call m the dimension and r the rank. Adding or subtracting rows produces a graph homomorphism to a graph with a matrix of smaller dimension, thereby giving an upper bound on the chromatic number of the original graph. In this article we develop the foundations of this method. As a demonstration of its utility, we provide an alternate proof of Payan's theorem, which states that a cubelike graph (i.e., a Cayley graph on the product Z 2 × ⋯ × Z 2 of the integers modulo 2 with itself finitely many times) cannot have chromatic number 3. In a series of follow-up articles using the method of Heuberger matrices, we completely determine the chromatic number in cases with small dimension and rank, as well as prove a generalization of Zhu's theorem on the chromatic number of 6-valent integer distance graphs. [ABSTRACT FROM AUTHOR]

We define, for any graph G = (V , E) , a boundary ∂ G ⊆ V. The definition coincides with what one would expected for the discretization of (sufficiently nice) Euclidean domains and contains all vertices from the Chartrand, Erwin, Johns & Zhang boundary. Moreover, it satisfies an isoperimetric principle stating that graphs with many vertices have a large boundary unless they contain long paths: we show that for graphs with maximaldegree Δ | ∂ G | ≥ 1 2 Δ | V | diam (G) . For graphs discretizing Euclidean domains, one has diam (G) ∼ | V | 1 / d and recovers the scaling of the classical Euclidean isoperimetric principle. [ABSTRACT FROM AUTHOR]

A graph is a cograph if and only if it has no induced path on 4 vertices. The twin reduction graph of a graph G is denoted by R G. In this article, we describe the Laplacian eigenvalues and eigenvectors of a cograph G using its twin reduction graph R G , and characterize cographs with even and odd integer eigenvalues, respectively. We provide a construction for the Laplacian cospectral cographs. Further, we provide a complete description of the Laplacian spectrum of H -join of graphs when H is a cograph, and then obtain bounds for the algebraic connectivity of such graphs. We also provide some interesting observations on Hadamard diagonalizable cographs. [ABSTRACT FROM AUTHOR]

In 1975, P. Erdős proposed the problem of determining the maximum number f (n) of edges in a graph on n vertices in which any two cycles are of different lengths. Let f ∗ (n) be the maximum number of edges in a simple graph on n vertices in which any two cycles are of different lengths. Let M n be the set of simple graphs on n vertices and f ∗ (n) edges in which any two cycles are of different lengths. Let m c (n) be the maximum cycle length for all G ∈ M n . In this paper, it is proved that for n sufficiently large, m c (n) ≤ 15 16 n. We make the following conjecture: Conjecture. lim n → ∞ m c (n) n = 0. [ABSTRACT FROM AUTHOR]

Introduced by Gutman & Trinajstić in 1972, the two well-known Zagreb indices efficiently determine the total π -electron energy of alternant hydrocarbons. The hyper-Zagreb index is a variant of the classical first Zagreb index. A tree is an acyclic graphical structure. A segment in a tree is equivalent to a vertex of degree two. This paper derives sharp upper and lower bounds on the hyper-Zagreb index of trees with given number of segments. We also characterize the corresponding trees achieving those bounds. The second part of the paper studies the predictive potential of the hyper-Zagreb index for determining physicochemical properties such as the enthalpies of combustion, formation, sublimation, and vaporization of monocarboxylic acids. Our statistical analysis asserts that the hyper-Zagreb index correlates these physicochemical properties of monocarboxylic acids with correlation coefficient ρ > 0.99. The strongest correlation by the hyper-Zagreb index was obtained with the enthalpy of combustion having correlation coefficient ρ = 0.999991. This warrants the further employability of the hyper-Zagreb index in QSPR modeling. This potential applicability justifies the construction of the hyper-Zagreb graphical index whose motivation of defining was purely mathematical. [ABSTRACT FROM AUTHOR]

For q ∈ R , the Q - matrix Q = Q q of a connected simple graph G = (V , E) is Q q = (q ∂ (x , y)) x , y ∈ V , where ∂ denotes the path-length distance. Describing the set π (G) consisting of those q ∈ R for which Q q is positive semidefinite is fundamental in asymptotic spectral analysis of graphs from the viewpoint of quantum probability theory. Assume that G has at least two vertices. Then π (G) is easily seen to be a nonempty closed subset of the interval [ − 1 , 1 ]. In this note, we show that π (G) = [ − 1 , 1 ] if and only if G is isometrically embeddable into a hypercube (infinite-dimensional if G is infinite) if and only if G is bipartite and does not possess certain five-vertex configurations, an example of which is an induced K 2 , 3. [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]

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 neural network is a computer system modeled on the nerve tissue and nervous system. In this sense, neural networks refer to systems of neurons, either organic or artificial in nature. Neural networks have diverse applications in computer graphics, artificial intelligence (AI), machine & deep learning, chemistry, material science, among others. Research on structural properties and their classification of favorable or unfavorable for neural networks has been started recently. Employing tools from mathematics and specifically graph theory has been a key research direction in this area. Different graph-theoretic parameters have potential applications in studying topological properties of neural networks. In this paper for the first time, we study some nondeterministic polynomial-time (NP)-complete and NP-hard problems on various neural networks by considering their graphs. We consider classes of 3- and 4-layered probabilistic neural networks (PNNs), cellular neural networks (CNNs), and Tickysym spiking neural networks (TSNNs). In order to study their topological properties, we study their structures of maximal cliques, minimal colorings, maximal independent sets, maximal and perfect matchings, and minimum dominating sets. Computational results on the clique number, chromatic number, independence number, matching ratio and the domination number are reported. For instance, the clique number of the probabilistic neural networks is 2, the Tickysym spiking neural network is 3, whereas, for the cellular neural network, it is 4. These numerical results quantify the incoming/outgoing traffic in these architectures. Similarly, the independence number of 25-nodal 3-layered probabilistic neural network is 15, whereas, the independence number of 25-nodal cellular neural network is just 9. Moreover, the asymptotic matching ratio for PNNs (resp. CNNs) is 1 2 (resp. 1 8 ), whereas, it is 1 6 for the case of TSNNs. This gives probabilistic neural networks a significant priority in controllability over cellular neural networks. Some open problems are proposed in the end to further this research area. [ABSTRACT FROM AUTHOR]

The extraction of the communities is reflected by the allocation of the nodes to the different communities and therefore a distribution, to which we can associate a score indicating its quality. Several methods have been proposed to extract existing communities in a network. The classification of these methods may be the subject of a separate study. The common point noted between most of these methods is the use of a function that measures the quality of a distribution. A metric called "Modularity" is considered to be the most efficient; it is used in most of the community extraction algorithms. Other metrics have been proposed such as "Z-Modularity", "Modularity density", "Exponential modularity". However, Modularity is still a competing metric. Our job is to establish an in-depth study of these quality measurement functions. For this purpose, considering the case of non-overlapping communities, we thought of a structural comparison between the results obtained, executing the "Leiden" algorithm, each time we change the metric among the four adopted. We chose this algorithm because it is an improved version of one of the most popular algorithms in this area called "Louvain". [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]

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]

Let Θ (G) denote the Shannon capacity of a graph G. We give an elementary proof of the equivalence, for any graphs G and H , of the inequalities Θ (G ⊔ H) > Θ (G) + Θ (H) and Θ (G ⊠ H) > Θ (G) Θ (H). This was shown independently by Wigderson and Zuiddam (2022) using Kadison–Dubois duality and the Axiom of choice. [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]

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]

Let G be a graph and T a spanning tree of G. For an edge e in G − T , there is a cycle in T ∪ { e }. We call those edges cycle-edges and those cycles tree-cycles. The intersection of two tree-cycles is the set of all edges in common. If the intersection of two distinct tree-cycles is not empty, we regard that as an intersection. The tree intersection number of T is the number of intersections among all tree-cycles of T. In this paper, we prove the conjecture, posed by Dubinsky et al. (2021), which states that if a graph admits a star spanning tree in which one vertex is adjacent to all other vertices, then the star spanning tree has the minimum tree intersection number. [ABSTRACT FROM AUTHOR]

We define a graph G as well-hued if for each positive integer k there is an integer a k such that every maximal k -colorable subgraph of G has order a k. This strengthens the notion of well-covered graphs. In this paper we investigate the connection between this property and related properties, characterize the sequences of the a k that can be achieved, and determine conditions for the property in some graph classes and under some graph operations such as products. [ABSTRACT FROM AUTHOR]

In communication networks, the existence of fractional factors can be characterized as the feasibility of data transmission. When some nonadjacent nodes with each other are damaged and a special channel is assigned, the possibility of data transmission in a communication network is equivalent to the existence of fractional ID-factor-critical covered graph. As a consequence, the existence of fractional ID- [ a , b ] -factor-critical covered graph plays a key role in studying data transmissions of communication networks. Neighborhood and minimum degree of a graph or a network are often used to measure the vulnerability and robustness of a graph or a network, which are two important parameters considered in network design. In this article, we mainly investigate the relationship between neighborhood of independent set, minimum degree and the fractional ID- [ a , b ] -factor-critical covered graph, and acquire a neighborhood of independent set and minimum degree condition for a graph being fractional ID- [ a , b ] -factor-critical covered, which is a generalization of the previous results. [ABSTRACT FROM AUTHOR]

A graph G is P ≥ k -factor deleted if for every edge e ∈ E (G) , G contains a P ≥ k -factor that excludes e. We first define the concept of (P ≥ k , n) -critical deleted graph, that is, a graph G is (P ≥ k , n) -critical deleted if for every subset D ⊆ V (G) with | D | = n , the graph G − D is P ≥ k -factor deleted. Clearly, a (P ≥ k , 0) -critical deleted graph is a P ≥ k -factor deleted graph. In this paper, we verify that (i) an (n + 2) -connected graph G is (P ≥ 2 , n) -critical deleted if its binding number b i n d (G) > 3 + n 4 ; (ii) an (n + 2) -connected graph G is (P ≥ 3 , n) -critical deleted if its binding number b i n d (G) > 3 + n 2 . Furthermore, we claim that two results above are best possible in some sense. [ABSTRACT FROM AUTHOR]

Data-driven approaches have been recognized as a new paradigm for establishing and exploring process-morphology-property relationships. However, typical exploration methods deliver high-dimensional morphologies that pose the challenge of extracting the key features and patterns that could guide the processing and materials design. The high dimensionality also hampers the organization of the data and the associated data analytics. As a solution, the currently available approaches either take a simplified view of the morphology, e.g., focusing on pixels in the morphology images, or apply transformations that average out structural descriptors of morphologies. To address these shortcomings, we propose a new computationally efficient and configurable distance operator that takes an intermediate approach. Our main idea is to represent the morphology as a graph where graph connectivity reflects the relative arrangement of components (e.g., grains, droplets) in the morphology, and the label of the graph vertices captures the domain-specific information of each characteristic domain. Next, given the graph abstraction, the distance between morphologies is computed using vectorized graph-based representation. Because both morphology graph structure and associated signature functions have clear interpretations, our distance measure can be easily tailored to specific applications. Our results demonstrate the superior performance of the proposed approach on data from simulation and synthetic data, including in real-world applications like morphologies clustering. [Display omitted] [ABSTRACT FROM AUTHOR]

Despite the significant progress for monocular 3D human pose estimation, it still faces challenges due to self-occlusions and depth ambiguities. To tackle those issues, we propose a novel Dynamic Graph Transformer (DGFormer) to exploit local and global relationships between skeleton joints for pose estimation. Specifically, the proposed DGFormer mainly consists of three core modules: Transformer Encoder (TE), immobile Graph Convolutional Network (GCN), and dynamic GCN. TE module leverages the self-attention mechanism to learn the complex global relationships among skeleton joints. The immobile GCN is responsible for capturing the local physical connections between human joints, while the dynamic GCN concentrates on learning the sparse dynamic K-nearest neighbor interactions according to different action poses. By building the adequately global long-range, local physical, and sparse dynamic dependencies of human joints, experiments on Human3.6M and MPI-INF-3DHP datasets demonstrate that our method can predict 3D pose with lower errors outperforming the recent state-of-the-art image-based performance. Furthermore, experiments on in-the-wild videos demonstrate the impressive generalization abilities of our method. Code will be available at: https://github.com/czmmmm/DGFormer. • We propose a novel dynamic Graph Transformer model for 3D human pose estimation (3D-HPE). • The Transformer is applied to exploit the global relationships among skeleton joints. • The proposed immobile GCN captures the local physical connections. • The proposed dynamic GCN learns the sparse dynamic K-nearest neighbor interactions. • Our method outperforms state-of-the-art methods for image-based 3D-HPE. [ABSTRACT FROM AUTHOR]

A k -edge coloring ϕ of graph G is injective if any two edges at distance 2 or in the same triangle get different colors. The minimum k in such an edge coloring is the injective edge chromatic number of G , written as χ i ′ (G). We prove in this paper that for any graph G with Δ (G) ≤ 5 , χ i ′ (G) ≤ 18 if m a d (G) < 16 5 , χ i ′ (G) ≤ 19 if m a d (G) < 7 2 and χ i ′ (G) ≤ 20 if m a d (G) < 15 4. • The results obtained in this paper enrich the previous work concerning on the study of injective coloring of sparse graphs. • The discharging method used in this paper is especially useful to solve the problem of injective coloring. • Some important reducible configurations are presented and the discharging rulers are well designed. • It is the first time to study the sufficient conditions for graphs with maximum degree Δ = 5 satisfying χ i ′ (G) ≤ Δ (Δ − 1). [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and A (G) be its adjacency matrix. The terms singularity, eigenvalues, and characteristic polynomial of G mean those of A (G). A nonsingular graph G is said to have the reciprocal eigenvalue property if the reciprocal of each eigenvalue of G is also an eigenvalue. A graph G (possibly singular) is said to have the weak reciprocal eigenvalue property if the reciprocal of each nonzero eigenvalue of it is also an eigenvalue. In Barik et al. (2022) [3] , the authors proved that there is no nontrivial tree with the weak reciprocal eigenvalue property and posed the following question: "Does there exist a nontrivial graph with the weak reciprocal eigenvalue property?" Suppose that G is singular and the characteristic polynomial of G is x n − k (x k + a 1 x k − 1 + ⋯ + a k). Assume that A (G) has rank k , so that a k ≠ 0. Can we ever have | a k | = 1 ? The answer turns out to be negative. As an application, we settle the question posed in Barik et al. (2022) [3]. Another similar application is also mentioned. It is natural to wonder, "Does there exist a nontrivial, simple, connected weighted graph with the weak reciprocal eigenvalue property?" We provide a class of such graphs. Furthermore, we extend our results to weighted graphs. [ABSTRACT FROM AUTHOR]

Wastewater treatment plant (WWTP) discharges of microcontaminants negatively impact freshwater streams, underscoring the need for accurately mapping wastewater-derived contamination in water bodies across Europe (EU). In this study, we present a fast and open-source code for a microcontaminants fate and transport (MFT) model, capable of simulating contamination at a high resolution (15 arc second scale) across the EU. The model was developed using the best publicly available hydrological (HydroSHEDS) and sanitation (UWWTD) datasets and was rigorously calibrated, with a goodness of fit of 77.5% as measured by the R 2. Importantly, the model demonstrated the ability to predict wastewater-derived contamination in water bodies, making it a valuable tool for planning the upgrade of WWTPs and improving the ecological condition of freshwater streams in the EU. • A model is developed to simulate wastewater-based contamination in rivers. • Large-scale free hydrologic and sanitation layers are used. • The model is calibrated obtaining an R2 of 77.5%. • The model is open-source and has fast runtimes. [ABSTRACT FROM AUTHOR]

A dominating set of a graph G = (V , E) is a subset of vertices S ⊆ V such that every vertex v ∈ V ∖ S has at least one neighbor in S. Finding a dominating set with the minimum cardinality in a connected graph G = (V , E) is known to be NP-hard. A polynomial-time approximation algorithm for this problem, described here, works in two stages. At the first stage a dominant set is generated by a greedy algorithm, and at the second stage this dominating set is purified (reduced). The reduction is achieved by the analysis of the flowchart of the algorithm of the first stage and a special kind of clustering of the dominating set generated at the first stage. The clustering of the dominating set naturally leads to a special kind of a spanning forest of graph G , which serves as a basis for the second purification stage. We expose some types of graphs for which the algorithm of the first stage already delivers an optimal solution and derive sufficient conditions when the overall algorithm constructs an optimal solution. We give three alternative approximation ratios for the algorithm of the first stage, two of which are expressed in terms of solely invariant problem instance parameters, and we also give one additional approximation ratio for the overall two-stage algorithm. The greedy algorithm of the first stage turned out to be essentially the same as the earlier known state-of-the-art algorithms for the set cover and dominating set problem Chvátal [6] and Parekh [31]. The second purification stage results in a significant reduction of the dominant set created at the first stage, in practice. The practical behavior of both stages was verified for randomly generated problem instances. The computational experiments emphasize the gap between a solution of Stage 1 and a solution of Stage 2. [ABSTRACT FROM AUTHOR]

In smart manufacturing, an increasing amount of heterogeneous data inputs need to be integrated into a holistic traceability model. One key challenge is the coherent mapping of dynamic and event-based sensor data for real-time tracking purposes with static data, which are mostly needed for retrospective tracing purposes. In this research, we develop a graph-based traceability model, which integrates static and dynamic data sub-models in one connected traceability graph. For an automotive use case, the novel traceability model is implemented and tested using a hybrid architecture based on the graph database Neo4j and the event engine Apache Kafka. [ABSTRACT FROM AUTHOR]

Schizophrenia is a severe mental disorder whose neural basis remains difficult to ascertain. Among the available pathophysiological theories, recent work has pointed towards subtle perturbations in the excitation-inhibition (E/I) balance within different neural circuits. Computational approaches have suggested interesting mechanisms that can account for both E/I imbalances and psychotic symptoms. Based on hierarchical neural networks propagating information through a message-passing algorithm, it was hypothesized that changes in the E/I ratio could cause a "circular belief propagation" in which bottom-up and top-down information reverberate. This circular inference (CI) was proposed to account for the clinical features of schizophrenia. Under this assumption, this paper examined the impact of CI on network dynamics in light of brain imaging findings related to psychosis. Using brain-inspired graphical models, we show that CI causes overconfidence and overactivation most specifically at the level of connector hubs (e.g., nodes with many connections allowing integration across networks). By also measuring functional connectivity in these graphs, we provide evidence that CI is able to predict specific changes in modularity known to be associated with schizophrenia. Altogether, these findings suggest that the CI framework may facilitate behavioral and neural research on the multifaceted nature of psychosis. [ABSTRACT FROM AUTHOR]