Search

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]

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]

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]

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]

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]

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]

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]

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]

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]

• 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]

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]

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]

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]

Toughness implies the topological representation characterization of network graphs. The pioneering works implicated that there are salient relationship between toughness and the existence of fractional factor in various settings. Specifically, Liu and Zhang (2008) [7] determined that G admits a fractional k -factor if t (G) ≥ k − 1 k and | V (G) | ≥ k + 1 (k ≥ 2 is an integer), and the toughness bound is tight. A graph G is fractional (k , n) -critical, if removing any n vertices from G the resulting subgraph still admits a fractional k -factor. In this paper, we prove that if k > n , then the original toughness condition (i.e., t (G) ≥ k − 1 k) is sufficient for a graph to be fractional (k , n) -critical. Furthermore, we explain why k > n is the extreme boundary to keep the original toughness bound. [ABSTRACT FROM AUTHOR]

Multiple kernel clustering (MKC) has been extensively studied in recent years. The focus of MKC is how to explore the information of base kernels. Although existing methods have promising leaning abilities, they ignore the intrinsic local structure contained in base kernels, which may negatively affect their performances. To address the above problem, a novel method, termed as consensus graph learning based on local kernels (CGLLK), is introduced. CGLLK is based on the partitions extracted by kernel k-means. Specifically, we first design a simple yet effective scheme to construct the local kernels of base kernels and then a consensus graph is applied to capture the complementary information contained in the extracted partitions of local kernels. CGLLK also considers the prior knowledge existing in base kernels. Since the partitions of local kernels and the learning stage of the consensus graph contain useful information for each other, the two processes are optimized jointly. Extensive experiments on some popular datasets are carried out to verify the effectiveness of the proposed method. Experimental results illustrate that CGLLK is much more competitive than the state-of-the-art algorithms. • A new scheme is designed to focus on the local neighbors of samples. • The clustering information existing in local kernels is captured by a consensus graph. • The processes of graph learning and partitions are incorporated into a unified framework. • The proposed method obviously outperforms the state-of-the-arts. [ABSTRACT FROM AUTHOR]

Let α ∈ [ 0 , 1) , and let G be a connected graph of order n with n ≥ f (α) , where f (α) = 14 for α ∈ [ 0 , 1 2 ] , f (α) = 17 for α ∈ (1 2 , 2 3 ] , f (α) = 20 for α ∈ (2 3 , 3 4 ] and f (α) = 5 1 − α + 1 for α ∈ (3 4 , 1). A spanning subgraph whose components are paths is said to be a path-factor. A P ≥ k -factor means a path-factor with each component being a path of order at least k , where k ≥ 2 is an integer. The A α -spectral radius of G is denoted by ρ α (G). In this paper, it is verified that G has a P ≥ 2 -factor if ρ α (G) > θ (n) , where θ (n) is the largest root of x 3 − ((α + 1) n + α − 5) x 2 + (α n 2 + (α 2 − 3 α − 1) n − 2 α + 1) x − α 2 n 2 + (7 α 2 − 5 α + 3) n − 18 α 2 + 29 α − 15 = 0. Furthermore, we provide a graph to show that the bound on A α -spectral radius is optimal. [ABSTRACT FROM AUTHOR]

Let G be a connected graph and let k be a positive integer. Let T be a spanning tree of G. The leaf degree of a vertex v ∈ V (T) is defined as the number of leaves adjacent to v in T. The leaf degree of T is the maximum leaf degree among all the vertices of T. Let D (G) and Q (G) denote the distance matrix and the distance signless Laplacian matrix of G , respectively. In this work, we provide the upper bounds for the spectral radius of D (G) (resp. Q (G)) in a connected graph G of order n to guarantee that G contains a spanning tree with leaf degree at most k. Furthermore, we establish some extremal graphs to show all the upper bounds obtained in this work are sharp. [ABSTRACT FROM AUTHOR]

For a non-decreasing sequence of integers (a 1 , a 2 , ... , a k) , an (a 1 , a 2 , ... , a k) -packing coloring of a graph G is a partition of V (G) into k subsets V 1 , V 2 , ... , V k such that the distance between any two distinct vertices x , y ∈ V i is at least a i + 1 , 1 ≤ i ≤ k. This paper studies the packing coloring of subcubic graphs. Gastineau and Togni (2016) [7] asked whether every subcubic graph except the Petersen graph is (1 , 1 , 2 , 3) -packing colorable. A subcubic graph G is said to be i -saturated, 0 ≤ i ≤ 2 , if every vertex of degree three in G has at most i neighbors of degree three and it is said to be 3-saturated if it is not 2-saturated. Besides, a vertex of degree three in a 3-saturated subcubic graph is said to be heavy if all its neighbors are of degree three. We prove that every 1-saturated subcubic graph is (1 , 1 , 2) -packing colorable. Moreover, we prove that a 3-saturated subcubic graph is (1 , 1 , 2 , 2) -packing colorable if any two of its heavy vertices are not adjacent. [ABSTRACT FROM AUTHOR]

The quality of polyester yarn is mainly affected by its dyeing uniformity. As a result, textile manufacturers need to inspect the dyeing uniformity of polyester yarn. The existing inspection methods rely on the dyeing process which can be viewed as a way to extract the discriminative information of the polyester yarns with different dyeing uniformities. However, the dyeing process is extremely time-consuming and laborious. It is very expensive to obtain the dyeing uniformities of polyester yarns, due to the inefficient dyeing process. To address this problem, an efficient and effective inspection method based on near-infrared imaging spectroscopy and semi-supervised learning is introduced in this paper. This introduced method can obtain the dyeing uniformity of polyester yarn without the dyeing process, which greatly boosts the efficiency of inspection. In the developed method, to acquire the representative information without the dyeing process, near-infrared spectra are applied to represent the molecular structure differences of different polyester yarns. Considering that the dyeing uniformities are expensive to obtain, a novel semi-supervised learning algorithm, termed consensus local graph based on multiple kernel learning (CLGMKL), is proposed in the introduced method to evaluate the dyeing uniformity of polyester yarn. Since redundant wavebands and noise exist in the collected spectra, the relationship among spectra in CLGMKL is learned based on the extracted low-rank matrices which contain the discriminative information of base kernels. Besides, CLGMKL incorporates the label information of spectra. Finally, extensive experiments on the collected spectra of polyester yarns demonstrate the superiority of the proposed method. • We use NIR spectra to represent the differences among PET yarns. • A novel semi-supervised learning algorithm is proposed to handle the spectra. • We can directly obtain the dyeing properties without the dyeing process. [ABSTRACT FROM AUTHOR]

• Developed a HSG-MGAF net to adaptively establish low-order and potential high-order spatial relationships of patches for interpretable prediction of giga-pixel WSI. • Embeds a Top-2k heterogeneous subgraph to guide hierarchical multi-scale graph framework for adaptive slide prediction and ROI localization. • Self-supervised contrastive learning constraint is introduced to maximize the consistency of predictions at heterogeneous scales in the optimization. • Interpretable heatmaps with complementary features can be obtained by using heterogeneous relationships of the top ranked patches at two scales. Pathological whole slide image (WSI) prediction and region of interest (ROI) localization are important issues in computer-aided diagnosis and postoperative analysis in clinical applications. Existing computer-aided methods for predicting WSI are mainly based on multiple instance learning (MIL) and its variants. However, most of the methods are based on instance independence and identical distribution assumption and performed at a single scale, which not fully exploit the hierarchical multiscale heterogeneous information contained in WSI. Heterogeneous Subgraph-Guided Multiscale Graph Attention Fusion Network (HSG-MGAF Net) is proposed to build the topology of critical image patches at two scales for adaptive WSI prediction and lesion localization. The HSG-MGAF Net simulates the hierarchical heterogeneous information of WSI through graph and hypergraph at two scales, respectively. This framework not only fully exploits the low-order and potential high-order correlations of image patches at each scale, but also leverages the heterogeneous information of the two scales for adaptive WSI prediction. We validate the superiority of the proposed method on the CAMELYON16 and the TCGA- NSCLC, and the results show that HSG-MGAF Net outperforms the state-of-the-art method on both datasets. The average ACC, AUC and F 1 score of HSG-MGAF Net can reach 92.7 %/0.951/0.892 and 92.2 %/0.957/0.919, respectively. The obtained heatmaps can also localize the positive regions more accurately, which have great consistency with the pixel-level labels. The results demonstrate that HSG-MGAF Net outperforms existing weakly supervised learning methods by introducing critical heterogeneous information between the two scales. This approach paves the way for further research on light weighted heterogeneous graph-based WSI prediction and ROI localization. [ABSTRACT FROM AUTHOR]

In this paper, we consider the edge searching problem and the fast searching problem with constraints on some vertices. The edge searching problem was introduced by Megiddo et al. (1988) [15] , in which a group of searchers want to capture an invisible robber. The fast searching problem was introduced by Dyer et al. (2008) [8]. One constraint we consider for these two searching models is that a subset of vertices, called start vertices, are initially occupied by searchers. We want to find the minimum number of additional searchers to capture the robber. Another constraint is that there are some vertices, called halt vertices, which have to be occupied by searchers at the end of the searching process. For the edge searching on a tree containing only start vertices, we propose an O (n log ⁡ n) -time algorithm for computing the edge search number, where n is the number of vertices. For the edge searching on a tree with start vertices and halt vertices, we give an O (n 2) -time algorithm to compute the edge search number. For the fast searching on a tree that contains only start vertices, we present a linear-time algorithm for computing the fast search number. For the fast searching on a tree with n vertices that contains s start vertices and h halt vertices, we propose an O ((s + h) n) -time algorithm to compute the fast search number. For the edge searching (respectively, fast searching) with only halt vertices, we reduce the problem to the edge searching (respectively, fast searching) with start vertices. [ABSTRACT FROM AUTHOR]

In this paper, we study the recently introduced scoring game played on graphs called the Edge-Balanced Index Game. This game is played on a graph by two players, Alice and Bob, who take turns colouring an uncoloured edge of the graph. Alice plays first and colours edges red, while Bob colours edges blue. The game ends once all the edges have been coloured. A player captures a vertex if more than half of its incident edges are coloured by that player, and the player that captures the most vertices wins. Using classical arguments from the field, we first prove general properties of this game. Namely, we prove that there is no graph in which Bob can win (if Alice plays optimally), while Alice can never capture more than 2 more vertices than Bob (if Bob plays optimally). Through dedicated arguments, we then investigate more specific properties of the game, and focus on its outcome when played in particular graph classes. Specifically, we determine the outcome of the game in paths, cycles, complete bipartite graphs, and Cartesian grids, and give partial results for trees and complete graphs. [ABSTRACT FROM AUTHOR]

For a simple graph G , let n (G) , η (G) , r (G) and g (G) be respectively the order, the nullity, the rank and the girth of G. It was shown by Cheng and Liu (2007) that for every graph G , η (G) ≤ { n (G) − g (G) + 2 if 4 | g (G) n (G) − g (G) if 4 ∤ g (G) . Connected graphs G with η (G) = n (G) − g (G) + 2 and n (G) − g (G) respectively have been characterized by Zhou et al. (2021). In this paper, we characterize connected graphs G with η (G) = n (G) − g (G) − 1. [ABSTRACT FROM AUTHOR]

The node reliability of a graph G is the probability that at least one node is operational and that the operational nodes can all communicate in the subgraph that they induce, given that the edges are perfectly reliable but each node operates independently with probability p ∈ [ 0 , 1 ]. We show that unlike many other notions of graph reliability, the number of maximal intervals of decrease in [ 0 , 1 ] is unbounded, and that there can be arbitrarily many inflection points in the interval as well. [ABSTRACT FROM AUTHOR]

The secure domination numbers of the Cartesian products of two small graphs with paths or cycles is determined, as well as for Möbius ladder graphs. Prior to this work, in all cases where the secure domination number has been determined, the proof has either been trivial, or has been derived from lower bounds established by considering different forms of domination. However, the latter mode of proof is not applicable for most graphs, including those considered here. Hence, this work represents the first attempt to determine secure domination numbers via the properties of secure domination itself, and it is expected that these methods may be used to determine further results in the future. [ABSTRACT FROM AUTHOR]

The connectivity and diagnosability of a system or an interconnection network are two important measures. As a topology structure of interconnection networks, the godan graph E A n has many good properties. In this paper, we give various connectivity of E A n and two diagnosability of E A n under the comparison diagnosis model. [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]