Search

Abstract Let G = (V , E) be a simple graph of order n with normalized Laplacian eigenvalues ρ 1 ≥ ρ 2 ≥ ⋯ ≥ ρ n − 1 ≥ ρ n = 0. The normalized Laplacian spread of graph G , denoted by ρ 1 − ρ n − 1 , is the difference between the largest and the second smallest normalized Laplacian eigenvalues of graph G. In this paper, we obtain the first four smallest values on ρ 2 of graphs. Moreover, we give a lower bound on ρ 2 of connected bipartite graph G except the complete bipartite graph and characterize graphs for which the bound is attained. Finally, we present some bounds on the normalized Laplacian spread of graphs and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

Abstract A path decomposition of a graph G is a collection of edge-disjoint paths of G that covers the edge set of G. Gallai (1968) conjectured that every connected graph on n vertices admits a path decomposition of cardinality at most ⌊ (n + 1) ∕ 2 ⌋. Gallai's Conjecture has been verified for many classes of graphs. In particular, Lovász (1968) verified this conjecture for graphs with at most one vertex with even degree, and Pyber (1996) verified it for graphs in which every cycle contains a vertex with odd degree. Recently, Bonamy and Perrett (2016) verified Gallai's Conjecture for graphs with maximum degree at most 5, and Botler et al. (2017) verified it for graphs with treewidth at most 3. In this paper, we verify Gallai's Conjecture for triangle-free planar graphs. [ABSTRACT FROM AUTHOR]

Highlights • Propose an algorithm to overcome the resolution limitation of traditional approaches. • Successfully detect communities from ring of cliques networks. • Detect communities from the benchmark LFR networks with high accuracies. • Extract communities from real world football game network and co-purchasing network. Abstract Community detection from networks is an emerging topic in modern network science. Communities are defined as clusters of nodes or vertices that share higher concentration of edges among themselves than sharing with other nodes in the network. Community structure is an important property of real systems and detecting communities enables us to better understand the underlying structure of the system. The most widely used method for community detection is modularity maximization which works by optimizing a quality function named modularity of the network partition. However, traditional modularity-based approaches generally have a resolution limit that prevents them from detecting communities that are sufficiently smaller compared to the whole network. In this work, we target to overcome the resolution limit of the modularity function by incorporating a weight term in the modularity formulation. We propose a community detection approach based on a community quality metric, named as weighted modularity. We validate the performance of the proposed method in several benchmark networks and show that the proposed method is promising in different settings. [ABSTRACT FROM AUTHOR]

Abstract 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 Koh et al. (2013), it is proved that if G is a graph of order n ≥ 4 and δ (G) ≥ 2 , then γ t r (G) ≤ n − n 4 3. It is further conjectured that this bound can be improved to γ t r (G) ≤ n − θ (n). In this paper we show that if G is a graph with no C 3 components and δ (G) ≥ 2 , then γ t r (G) ≤ n − n 2 . [ABSTRACT FROM AUTHOR]

Abstract Feature selection can efficiently identify the most informative features with respect to the target feature used in training. However, state-of-the-art vector-based methods are unable to encapsulate the relationships between feature samples into the feature selection process, thus leading to significant information loss. To address this problem, we propose a new graph-based structurally interacting elastic net method for feature selection. Specifically, we commence by constructing feature graphs that can incorporate pairwise relationship between samples. With the feature graphs to hand, we propose a new information theoretic criterion to measure the joint relevance of different pairwise feature combinations with respect to the target feature graph representation. This measure is used to obtain a structural interaction matrix where the elements represent the proposed information theoretic measure between feature pairs. We then formulate a new optimization model through the combination of the structural interaction matrix and an elastic net regression model for the feature subset selection problem. This allows us to (a) preserve the information of the original vectorial space, (b) remedy the information loss of the original feature space caused by using graph representation, and (c) promote a sparse solution and also encourage correlated features to be selected. Because the proposed optimization problem is non-convex, we develop an efficient alternating direction multiplier method (ADMM) to locate the optimal solutions. Extensive experiments on various datasets demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Abstract The itemset is a basic and usual form of data. People can obtain new insights into their business by discovering its implicit regularities through pattern mining. In some real applications, e.g., network alarm association, the itemsets usually have the following two characteristics: (1) the observed samples come from different entities, with inherent structural relationships implied in their static properties; (2) the samples are scarce, which may lead to incomplete pattern extraction. This paper considers how to efficiently find a concise set of patterns on such kind of data. Firstly, we use a graph to express the entities and their interconnections and propagate every sample to every node with a weight, determined by the pre-defined combination of kernel functions based on the similarities of the nodes and patterns. Next, the weight values can be naturally imported into the MDL-based filtering process and bring a differentiated pattern set for each node. Experiments show that the solution can outperform the global solution (trading all nodes as one) and isolated solution (removing all edges) on simulated and real data, and its effectiveness and scalability can be further verified in the application of large-scale network operation and maintenance. [ABSTRACT FROM AUTHOR]

Abstract Mahlmann and Schindelhauer (2005) defined a Markov chain which they called k -Flipper, and showed that it is irreducible on the set of all connected regular graphs of a given degree (at least 3). We study the 1-Flipper chain, which we call the flip chain, and prove that the flip chain converges rapidly to the uniform distribution over connected 2 r -regular graphs with n vertices, where n ≥ 8 and r = r (n) ≥ 2. Formally, we prove that the distribution of the flip chain will be within ε of uniform in total variation distance after poly (n , r , log (ε − 1)) steps. This polynomial upper bound on the mixing time is given explicitly, and improves markedly on a previous bound given by Feder et al. (2006). We achieve this improvement by using a direct two-stage canonical path construction, which we define in a general setting. This work has applications to decentralised networks based on random regular connected graphs of even degree, as a self-stabilising protocol in which nodes spontaneously perform random flips in order to repair the network. [ABSTRACT FROM AUTHOR]

Abstract The fixing number of a graph Γ is the minimum number of labeled vertices that, when fixed, remove all nontrivial automorphisms from the automorphism group of Γ. The fixing set of a finite group G is the set of all fixing numbers of graphs whose automorphism groups are isomorphic to G. Previously, authors have studied the fixing sets of both abelian groups and symmetric groups. In this article, we determine the fixing set of the dihedral group. [ABSTRACT FROM AUTHOR]

Highlights • Optimal configuration requires minimum number of CFD calculations. • The set covering approaches ensures 100% coverage for a given length of the optimisation mesh. • CFD simulations are not mandatory for optimisation of gas detectors. • High performance and low computational cost. • 3D visualisation of the final configuration of gas detectors. Abstract An approach to optimise the number and location of gas detectors was developed based on the colour pattern of the graph of the set covering problem (SCP). The optimisation problem is combined to Computational Fluid Dynamics (CFD) data and the discrete optimisation problem is solved using Balas algorithm in the framework of a developed Fortran code. Every computational cell is regarded as a node of a graph where the links are the common boards shared by the neighbouring cells. The graph is read into the code via a dedicated algorithm for generation of the set of constrains. The characteristic length that determines the distance among the nodes of the graph is obtained from the set of CFD simulations or any stablished criterion. This work is based on the discovery of the colour pattern observed in the adjacency matrix that represents the set of constrains of the optimisation formulation and also on the limited set of gas dispersion CFD simulations to ensure full coverage of the area. Two cases (covering problem and p-median problem) are used in the validation of the developed code. Results are compared with the results obtained using CPLEX. Additional tests are considered ranging from simple 2D cases with 4 nodes up to 75 nodes. Two real engineering cases are considered and the efficiency of the method is discussed based on the volume of the cloud detected and the time to detection. Results show an efficient method for optimisation of gas detectors able to detect flammable clouds as small as a few cubic meters within 10 seconds. [ABSTRACT FROM AUTHOR]

Abstract The units forms are algebraic expressions that have important role in representation theory of algebras. We identified that existing algorithms have exponential time complexity for weakly nonnegative and weakly positive types. In this paper we introduce a polynomial algorithm for the recognition of weakly nonnegative unit forms. The related algorithm identifies hypercritical restrictions in a given unit form, testing every subgraph of 9 vertices of the unit form associated graph. By adding Depth First Search approach, a similar strategy could be used in the recognition of weakly positive unit forms. We also present the most popular methods to decide whether or not a unit form is weakly nonnegative or weakly positive, we analyze their time complexity and we compare the results with our algorithms. [ABSTRACT FROM AUTHOR]

Abstract We investigate the change in the multiplicities of the eigenvalues of a Hermitian matrix with a simple graph G , when edges are inserted into G or removed from G. We focus upon cases in which the multiplicity of the eigenvalue does not change due to inserting or removing edges incident to a vertex. Furthermore, we show how the change in the multiplicities of the eigenvalues occur, when two disjoint graphs are connected with one edge, based upon the status of the vertices that are connected. Lastly, we give the possible classifications of cut-edges in a graph and characterize the occurrence of each possible status. [ABSTRACT FROM AUTHOR]

Abstract A spanning tree of a graph is a connected subgraph on all vertices with the minimum number of edges. The number of spanning trees in a graph G is given by Matrix Tree Theorem in terms of principal minors of Laplacian matrix of G. We show a similar combinatorial interpretation for principal minors of signless Laplacian Q. We also prove that the number of odd cycles in G is less than or equal to det ⁡ (Q) 4 , where the equality holds if and only if G is a bipartite graph or an odd-unicyclic graph. [ABSTRACT FROM AUTHOR]

Abstract This paper proposes and explores a new quantitative characterization of the polarization phenomenon in networks. New tools for evaluating the polarization of a network are presented. We first characterize the homophily of each node individually. We depart from the definition of a new measure of the homophily of the nodes of a network and we consider the homophily distribution over the nodes as a primary indicator of the strength of polarization. Next, to address the polarization of the network as a whole, a probabilistic approach is developed. The approach is based on the straightforward computation of empirical cumulative distribution functions of sampled data from the network. These empirical distributions provide a more insightful understanding of the status of the network. They may be used not only to compare the polarization of groups of nodes or entire networks, but also to estimate the impacts of external interventions in terms of node polarization. The usefulness of the approach is illustrated on several case studies associated with real-life data sets from different sources. [ABSTRACT FROM AUTHOR]

Abstract We revisit the numerical quaternionic study on the mean-square radius of gyration and the hydrodynamic radius for topological or graph-shaped polymers. We show that it is consistent with other approaches although we apply a nontrivial modification of the quaternionic method [51] for generating random polygons. In the modified method we generate random walks that connect two given points by rescaling the bond length and assign them some weight. We evaluate by it the mean-square radius of gyration and the hydrodynamic radius for several topological polymers. We correct the plots of Ref. [46] for the hydrodynamic radius versus the segment number and for the ratio of the gyration to the hydrodynamic radius versus the segment number. The estimated ratios are close to the values derived from an analytic assumption of the pair distribution function. The gyration radius of the multi-theta chain evaluated by the modified method agrees with exact Gaussian results [48]. We derive the moments of the bond vectors' coordinates distribution in random polygons generated by the quaternionic method. [ABSTRACT FROM AUTHOR]

Abstract Plasticity is one of the most important properties of the nervous system, which enables animals to adjust their behavior to the ever-changing external environment. Changes in synaptic efficacy between neurons constitute one of the major mechanisms of plasticity. Therefore, estimation of neural connections is crucial for investigating information processing in the brain. Although many analysis methods have been proposed for this purpose, most of them suffer from one or all the following mathematical difficulties: (1) only partially observed neural activity is available; (2) correlations can include both direct and indirect pseudo-interactions; and (3) biological evidence that a neuron typically has only one type of connection (excitatory or inhibitory) should be considered. To overcome these difficulties, a novel probabilistic framework for estimating neural connections from partially observed spikes is proposed in this paper. First, based on the property of a sum of random variables, the proposed method estimates the influence of unobserved neurons on observed neurons and extracts only the correlations among observed neurons. Second, the relationship between pseudo-correlations and target connections is modeled by neural propagation in a multiplicative manner. Third, a novel information-theoretic framework is proposed for estimating neuron types. The proposed method was validated using spike data generated by artificial neural networks. In addition, it was applied to multi-unit data recorded from the CA1 area of a rat's hippocampus. The results confirmed that our estimates are consistent with previous reports. These findings indicate that the proposed method is useful for extracting crucial interactions in neural signals as well as in other multi-probed point process data. [ABSTRACT FROM AUTHOR]

Abstract Let X be a local dendrite and let f : X → X be a monotone map. Denote by P (f) and Ω (f) the sets of periodic points and nonwandering points of f , respectively. We show that Ω (f) = P (f) ‾ , whenever P (f) is nonempty and Ω (f) is the unique minimal set included in a circle which is either a Cantor set or a circle, whenever P (f) is empty. In the case where the set of endpoints of X is countable, we show that Ω (f) = P (f) whenever P (f) is nonempty. [ABSTRACT FROM AUTHOR]

Abstract In this work, we introduce the graph regularized autoencoder. We propose three variants. The first one is the unsupervised version. The second one is tailored for clustering, by incorporating subspace clustering terms into the autoencoder formulation. The third is a supervised label consistent autoencoder suitable for single label and multi-label classification problems. Each of these has been compared with the state-of-the-art on benchmark datasets. The problems addressed here are image denoising, clustering and classification. Our proposed methods excel of the existing techniques in all of the problems. [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n and size m with Laplacian eigenvalues μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n = 0 . The Kirchhoff index of G , denoted by Kf , is defined as: K f = n ∑ i = 1 n − 1 1 μ i . The Laplacian-energy-like invariant ( L E L ) and the Laplacian energy ( L E ) of the graph G , are defined as: L E L = ∑ i = 1 n − 1 μ i and L E = ∑ i = 1 n | μ i − 2 m n | , respectively. We obtain two relations on LEL with Kf , and LE with Kf . For two classes of graphs, we prove that L E L > K f . Finally, we present an upper bound on the ratio L E / L E L and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

Berge’s Lemma says that for each independent set S and maximum independent set X , there is a matching from S − X into X − S , namely, a function of S − X into X − S such that ( s , f ( s ) ) is an edge for each s ∈ S − X . Levit and Mandrescu prove A Set and Collection Lemma. It is a strengthening of Berge’s Lemma, by which one can obtain a matching M : S − ⋂ Γ → ⋃ Γ − S , where S is an independent set and Γ is a collection of maximum independent sets. Jarden, Levit and Mandrescu invoke new inequalities from A Set and Collection Lemma and yield a new characterization of König–Egerváry graphs. In the current paper, we study Berge systems (collections of vertex sets, where the conclusion of Berge’s Lemma hold). The work is divided into two parts: the general theory of Berge systems and Berge systems associated with groups (or more precisely, in non-commuting graphs). We first show that there exists many Berge systems. The notion of an ideal is central in several branches of mathematics. We define ‘a graph ideal’, which is a natural generalization of ‘an ideal’ in the context of graph theory. We show that every graph ideal carries a Berge system. We prove a sufficient condition for a Berge system to be a multi-matching system (collections where the conclusion of a Set and Collection Lemma holds). We get new inequalities in multi-matching systems. Here, we do a turn about from the general theory of Berge systems into the study of Berge systems in non-commuting graphs. We prove that for every group G , if A and B are maximal abelian subsets of 〈 A , B 〉 G and | A | ≤ | B | , then there is a non-commutative matching of A − B into B − A . It means that every non-commuting graph carries a Berge system. Moreover, we apply the sufficient condition to get a multi-matching system in the context of non-commuting graphs and invoke new inequalities in group theory. Surprisingly, the new results concerning groups, do not hold for rings. [ABSTRACT FROM AUTHOR]

• We explore the impact of noise on pairwise similarity and affinity propagation among superpixels. • Different affinity graphs are combined according to the subspace-preserving representation of superpixels. • An online low-rank representation based-graph is proposed to improve segmentation accuracy and reduce computational complexity. Affinity graph-based segmentation methods have become a major trend in computer vision. The performance of these methods rely on the constructed affinity graph, with particular emphasis on the neighborhood topology and pairwise affinities among superpixels. However, these graph-based methods ignore the noisy data from images, that influence the accuracy of pairwise similarities. Multiscale combinatorial grouping and graph fusion also generate a higher computational complexity. In this paper, we propose an adaptive fusion affinity graph with noise-free low-rank representation in an online manner for natural image segmentation. An input image is first over-segmented into superpixels at different scales and then filtered by an improved kernel density estimation method. Moreover, we select global nodes of these superpixels on the basis of their subspace-preserving presentation, which reveals the feature distribution of superpixels exactly. To reduce time complexity while improving performance, a sparse representation of global nodes based on noise-free online low-rank representation is used to obtain a global graph at each scale. Experimental results on BSD300, BSD500, MSRC, SBD, and PASCAL VOC show the effectiveness of our method in comparison with the state-of-the-art approaches. The code is available at https://github.com/Yangzhangcst/AFA-graph. [ABSTRACT FROM AUTHOR]

As the demand for 3D models increases, there is growing interest in reconstructing 3D objects from images using AI. In this paper, we propose G2IFu, a graph-based implicit function that successfully reconstructs a highly detailed 3D object mesh from a single image. Unlike previous methods that learn implicit functions with points, G2IFu aims to map graphs to implicit values. We make the following contributions: (1) Compared to independent 3D points, graphs have a larger perception space and contain specific spatial structure information. Therefore, we extend a 3D point p to a graph G p by generating hypothesis points and establishing edges between them. We then predict the corresponding implicit value using a graph convolution network. Our experiments show that this method can effectively improve the prediction accuracy of implicit functions. (2) We introduce a prior boundary loss based on G p to make the network pay more attention to the "key" points near the shape surface. To the best of our knowledge, G2IFu is the first model that introduces a graph into neural implicit representation. (3) Inspired by previous methods, we utilize the image's global and local features to initialize G p. We also introduce a self-attention module into G2IFu for better performance. We conduct experiments on the ShapeNet dataset and demonstrate that G2IFu can generate higher-quality 3D object shapes than previous single-view reconstruction methods. Additionally, we extend G2IFu to multi-view 3D reconstruction and achieve good performance. [ABSTRACT FROM AUTHOR]

In this paper we introduce the graph Γ s c (G) associated with a group G , called the solvable conjugacy class graph (abbreviated as SCC-graph), whose vertices are the nontrivial conjugacy classes of G and two distinct conjugacy classes C , D are adjacent if there exist x ∈ C and y ∈ D such that 〈 x , y 〉 is solvable. We discuss the connectivity, girth, clique number, and several other properties of the SCC-graph. One of our results asserts that there are only finitely many finite groups whose SCC-graph has given clique number d , and we find explicitly the list of such groups with d = 2. We pose some problems on the relation of the SCC-graph to the solvable graph and to the NCC-graph, which we cannot solve. [ABSTRACT FROM AUTHOR]

The impact of different lockdown strategies upon the total number of infections in an epidemic are evaluated for two models of infection: one in which the disease confers permanent immunity, and one in which it does not. The strategies are based upon the proportion of the population infected at a time in order to trigger lockdown, combined with the proportion of interactions removed during lockdown. The population, its interactions, and the relative strengths of those interactions are stored in a weighted contact network, from which edges are removed during lockdown. These edges are selected using an evolutionary algorithm (EA) designed to minimize total infections. Using the EA to select edges significantly reduces total infections in comparison to random selection. In fact, the EA results for the least strict conditions were similar or better to the random results for the most strict conditions, showing that a judicious choice of restrictions during lockdown has the greatest effect on reducing infections. Further, when using the most strict rules a smaller proportion of interactions can be removed to obtain similar or better results in comparison to removing a higher proportion of interactions for less strict rules. [ABSTRACT FROM AUTHOR]

A k -independent set in a connected graph is a set of vertices such that any two vertices in the set are at distance greater than k in the graph. The k -independence number of a graph, denoted α k , is the size of a largest k -independent set in the graph. Recent results have made use of polynomials that depend on the spectrum of the graph to bound the k -independence number. They are optimized for the cases k = 1 , 2. There are polynomials that give good (and sometimes) optimal results for general k , including case k = 3. In this paper, we provide the best possible bound that can be obtained by choosing a polynomial for case k = 3 and apply this bound to well-known families of graphs including the Hamming graph. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we show a very close relationship between the compaction, vertex-compaction, and retraction problems for reflexive and bipartite graphs. Similar to a long-standing open problem concerning whether the compaction and retraction problems are polynomially equivalent, the relationships that we present relate to our problems concerning whether the compaction and vertex-compaction problems are polynomially equivalent, and whether the vertex-compaction and retraction problems are polynomially equivalent. The relationships that we present also relate to the constraint satisfaction problem, providing evidence that similar to the compaction and retraction problems, it is also likely to be difficult to give a complete computational complexity classification of the vertex-compaction problem for every fixed reflexive or bipartite graph. In this paper, we however give a complete computational complexity classification of the vertex-compaction problem for all graphs, including even partially reflexive graphs, with four or fewer vertices, by giving proofs based on mostly just knowing the computational complexity classification results of the compaction problem for such graphs determined earlier by the author. Our results show that the compaction, vertex-compaction, and retraction problems are polynomially equivalent for every graph with four or fewer vertices. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph of order n with m edges. Denote by D ( G ) the diagonal matrix of its vertex degrees and by A ( G ) its adjacency matrix. Then the Laplacian matrix of graph G is L ( G ) = D ( G ) − A ( G ) . Among all eigenvalues of the Laplacian matrix L ( G ) of graph G , the most studied is the second smallest, called the algebraic connectivity a ( G ) of a graph. Let d ‾ ( G ) and δ ( G ) be the average degree and the minimum degree of graph G , respectively. In this paper we characterize all graphs for which ( i ) a ( G ) = 1 with δ ( G ) ≥ ⌈ n − 1 2 ⌉ , and ( i i ) a ( G ) = 2 with δ ( G ) ≥ n 2 . In [1] , Aouchiche mentioned a conjecture involving the algebraic connectivity a ( G ) and the average degree d ‾ ( G ) of graph G : a ( G ) − d ‾ ( G ) ≥ 4 − n − 4 n with equality holding if and only if G ‾ ≅ K 1 , n − 2 ∪ K 1 ( K 1 , n − 2 is a star of order n − 1 and G ‾ is the complement of graph G ). Here we prove this conjecture. [ABSTRACT FROM AUTHOR]

By the well-known Perron–Frobenius Theorem [3] , for a connected graph G , its largest eigenvalue strictly increases when an edge is added. We are interested in how the other eigenvalues of a connected graph change when edges are added. Examples show that all cases are possible: increased, decreased, unchanged. In this paper, we consider the effect on the eigenvalues by suitably adding edges in particular families, say the family of connected graphs with clusters. By using the result, we also consider the effect on the energy by suitably adding edges to the graphs of the above families. [ABSTRACT FROM AUTHOR]

In this paper we demonstrate that the result by Zelikovskij concerning Königs problem for abelian permutation groups, reported in a recent survey, is false. We propose in this place two results on 2-closed abelian permutation groups which concern the same topic in a more general setting. [ABSTRACT FROM AUTHOR]

In this paper we describe the automorphism groups of graphs and edge-colored graphs that are cyclic as permutation groups. In addition, we show that every such group is the automorphism group of a complete graph whose edges are colored with 3 colors, and we characterize those groups that are automorphism groups of simple graphs. [ABSTRACT FROM AUTHOR]

Background and Objective: It can be challenging to delineate the target object in anatomical imaging when the object boundaries are difficult to discern due to the low contrast or overlapping intensity distributions from adjacent tissues. Methods: We propose a topo-graph model to address this issue. The first step is to extract a topographic representation that reflects multiple levels of topographic information in an input image. We then define two types of node connections - nesting branches (NBs) and geodesic edges (GEs). NBs connect nodes corresponding to initial topographic regions and GEs link the nodes at a detailed level. The weights for NBs are defined to measure the similarity of regional appearance, and weights for GEs are defined with geodesic and local constraints. NBs contribute to the separation of topographic regions and the GEs assist the delineation of uncertain boundaries. Final segmentation is achieved by calculating the relevance of the unlabeled nodes to the labels by the optimization of a graph-based energy function. We test our model on 47 low contrast CT studies of patients with non-small cell lung cancer (NSCLC), 10 contrast-enhanced CT liver cases and 50 breast and abdominal ultrasound images. The validation criteria are the Dice's similarity coefficient and the Hausdorff distance. Results: Student's t -test show that our model outperformed the graph models with pixel-only, pixel and regional, neighboring and radial connections ( p -values <0.05). Conclusions: Our findings show that the topographic representation and topo-graph model provides improved delineation and separation of objects from adjacent tissues compared to the tested models. [ABSTRACT FROM AUTHOR]

Currently, societal and technological trends make decision-making environments more and more complex. Linguistic variables are used to enrich the assessment of decision makers. This fact leads to the computational techniques of unbalanced linguistic terms for group decision making in the literature. First, we redefine the concept of unbalanced linguistic term set. We use three vertices in a graph based on a uniformly distributed term set to represent the left, central, and right parts of an unbalanced linguistic term set. Our definition makes unbalanced linguistic terms more arbitrary compared with previous definitions. We combine the 2-tuple linguistic model to construct an approximation representation model, which pursues computational convenience and concision at the expense of accuracy. Second, we propose a distance measure between two vertices on the graph and prove its reasonability. We extend this measure to aggregate preference of unbalanced linguistic terms provided by decision makers. Finally, a numerical example is given to illustrate the feasibility and validity of the proposed model. Our methodology allows a decision maker to use diversified assessment spaces to construct his/her preference. Furthermore, by using the aggregated geodesic distance to measure the ranking of alternatives, the slight difference in assessments can be noticed and reflected in the ranking. [ABSTRACT FROM AUTHOR]

The problem of efficiently sampling from a set of (undirected, or directed) graphs with a given degree sequence has many applications. One approach to this problem uses a simple Markov chain, which we call the switch chain, to perform the sampling. The switch chain is known to be rapidly mixing for regular degree sequences, both in the undirected and directed setting. We prove that the switch chain for undirected graphs is rapidly mixing for any degree sequence with minimum degree at least 1 and with maximum degree d max which satisfies 3 ≤ d max ≤ 1 3 M , where M is the sum of the degrees. The mixing time bound obtained is only a factor n larger than that established in the regular case, where n is the number of vertices. Our result covers a wide range of degree sequences, including power-law density-bounded graphs with parameter γ > 5 / 2 and sufficiently many edges. For directed degree sequences such that the switch chain is irreducible, we prove that the switch chain is rapidly mixing when all in-degrees and out-degrees are positive and bounded above by 1 4 m , where m is the number of arcs, and not all in-degrees and out-degrees equal 1. The mixing time bound obtained in the directed case is an order of m 2 larger than that established in the regular case. [ABSTRACT FROM AUTHOR]

Now define S a cartesian product of finite times with S M n which is a finite semigroup having elements { 0 , x , x 2 , … , x n } of order n . Γ( S ) is an undirected graph whose vertices are the nonzero elements of S . It is a new graph type which is the dot product. k be finite positive integer for 0 ≤ { i t } t = 1 k , { j t } t = 1 k ≤ n , any two distinct vertices of S ( x i 1 , x i 2 , … , x i k ) and ( x j 1 , x j 2 , … , x j k ) are adjacent if and only ( x i 1 , x i 2 , … , x i k ) · ( x j 1 , x j 2 , … , x j k ) = 0 S M n (under the dot product) and it is assumed x i t = 0 S M n if i t = 0 . In this study, the value of diameter, girth, maximum and minimum degrees, domination number, clique and chromatic numbers and in parallel with perfectness of Γ( S ) are elucidated. [ABSTRACT FROM AUTHOR]

The independence polynomial i ( G , x ) of a graph G is the generating function of the numbers of independent sets of each size. A graph of order n is very well-covered if every maximal independent set has size n ∕ 2 . Levit and Mandrescu conjectured that the independence polynomial of every very well-covered graph is unimodal (that is, the sequence of coefficients is nondecreasing, then nonincreasing). In this article we show that every graph is embeddable as an induced subgraph of a very well-covered graph whose independence polynomial is unimodal, by considering the location of the roots of such polynomials. [ABSTRACT FROM AUTHOR]

Let k be a positive integer. In this paper, we prove that for a graph G with at least 4 k vertices, if max { d ( x ) , d ( y ) } ≥ 2 k for any pair of nonadjacent vertices { x , y } ⊆ V ( G ) , then G contains k disjoint cycles. This generalizes the results given by Corr á di and Hajnal (1963), Enomoto (1998), and Wang (1999). [ABSTRACT FROM AUTHOR]

The inherent structure and connectivity of a group are important features of social networks. Finding the densest subgraphs of a graph directly maps to revealing the densest communities of a social network. Various techniques, e.g., edge density, k -core, near-cliques and k -cliques, have been developed to characterize graphs and extract the densest subgraphs of the graphs. However, as extraction of subgraphs with constraints is NP-hard, these techniques face a major difficulty of processing big and/or streaming data sets from social networks. This demands new methods from the expert and intelligent systems perspective for computation of the densest subgraph problem (DSP) with big and/or streaming data. The most recent method for this purpose is the “Sampling” method. It samples the big data sets, thus reducing the data space and consequently speeding up the DSP computation. But the sampled data inevitably miss out many useful data items. A new approach is presented in this paper for accelerated DSP computation with big and/or steaming data through data space reduction without loss of useful information. It uses a sliding window of small graphs with a fixed number of edges. Then, it filters out the least connected edges for each small graph. While the small graphs are processed, subgraphs are incrementally put together to reveal the densest subgraphs. Finally, the data space previously filtered out is checked for recovery of globally important edges. The approach is incorporated with existing subgraph extraction techniques for scalable and efficient DSP computation with improved accuracy. It is demonstrated for four subgraph extraction techniques over four Twitter data sets, and is shown to outperform the “sampling” method. [ABSTRACT FROM AUTHOR]

Visual tools are implemented to help users in defining how to generate Linked Data from raw data. This is possible thanks to mapping languages which enable detaching mapping rules from the implementation that executes them. However, no thorough research has been conducted so far on how to visualize such mapping rules, especially if they become large and require considering multiple heterogeneous raw data sources and transformed data values. In the past, we proposed the RMLEditor, a visual graph-based user interface, which allows users to easily create mapping rules for generating Linked Data from raw data. In this paper, we build on top of our existing work: we (i) specify a visual notation for graph visualizations used to represent mapping rules, (ii) introduce an approach for manipulating rules when large visualizations emerge, and (iii) propose an approach to uniformly visualize data fraction of raw data sources combined with an interactive interface for uniform data fraction transformations. We perform two additional comparative user studies. The first one compares the use of the visual notation to present mapping rules to the use of a mapping language directly, which reveals that the visual notation is preferred. The second one compares the use of the graph-based RMLEditor for creating mapping rules to the form-based RMLx Visual Editor, which reveals that graph-based visualizations are preferred to create mapping rules through the use of our proposed visual notation and uniform representation of heterogeneous data sources and data values. [ABSTRACT FROM AUTHOR]

Let n ≥ k ≥ 2 be two integers and S a subset of { 0 , 1 , … , k − 1 } . The graph J S ( n , k ) has as vertices the k -subsets of the n -set [ n ] = { 1 , … , n } and two k -subsets A and B are adjacent if | A ∩ B | ∈ S . In this paper, we use Godsil–McKay switching to prove that for m ≥ 0 , k ≥ max ⁡ ( m + 2 , 3 ) and S = { 0 , 1 , . . . , m } , the graphs J S ( 3 k − 2 m − 1 , k ) are not determined by spectrum and for m ≥ 2 , n ≥ 4 m + 2 and S = { 0 , 1 , . . . , m } the graphs J S ( n , 2 m + 1 ) are not determined by spectrum. We also report some computational searches for Godsil–McKay switching sets in the union of classes in the Johnson scheme for k ≤ 5 . [ABSTRACT FROM AUTHOR]

In this paper, we give some bounds on the signless Laplacian index of graphs in terms of independence number. In addition, these results disprove a conjecture in [3] involving the signless Laplacian index and independence number of graphs. [ABSTRACT FROM AUTHOR]

In Web Service Composition, services or APIs from multiple and independent providers are combined to create new functionality. Web Service Challenges have formalized the problem at a series of events where the community competed with various solutions. The composition problem has been incrementally extended adding more expressiveness and since 2006 the semantic aspect was addressed by the use of ontologies for service parameter description. In this paper, we propose a polynomial-time algorithm based on graph search, that solves the 2008 challenge. The algorithm uses a heuristic to address the NP-Hard problem of optimizing the number of services selected. Experimental results show that our solution is several times faster and generates shorter compositions on all evaluation tests compared with all winning solutions of the competition. Also, it is up to 50 times faster and very close to generate shortest compositions on the tests, compared with the solution published in 2011, that generates optimal compositions. [ABSTRACT FROM AUTHOR]

In Alberto and Mateo [2] , 2004, a graph-based structure used for manipulating populations of Multi-Objective Evolutionary Algorithms in a more efficient way than the structures existing at that point was defined. In this paper, an improvement of such tool is presented. It consists of the simultaneous insertion of a set of solutions (solution batch), instead of a single one, into the created graph structure. Furthermore, two experiments devoted to comparing the behavior of the new algorithms with the original version from Alberto and Mateo [2] and with a well-known non-dominated sorting algorithm are carried out. The first shows how the new version outperforms the original one in time and number of Pareto comparisons. The second experiment shows a reduction in the time needed in all the cases and an important reduction in the number of Pareto comparisons when inserting chains of dominated solutions. From these experiments it is verified that, in general, the new proposals save computational time and, in the majority of the cases, the number of Pareto comparisons carried out for the insertion. In addition, when the new proposals outperform the others, they increase their gain over them as the size of the population and/or the size of the batch increases. The new tool can also be used, for example, in parallel genetic algorithms such as the ones based on islands, to carry out the migrations of the solutions. [ABSTRACT FROM AUTHOR]

Finding all the graphs with a certain number of Q -main eigenvalues is an algebraic graph theory problem that scientists have sought to answer it for many years. The purpose of this research is finding relationships between the algebraic properties of a signless Laplacian matrix of a graph and the other properties of that graph. In order to achieve this, we choose to characterize all the unicyclic and bicyclic graphs with exactly three distinct Q -main eigenvalues, one of which is zero. [ABSTRACT FROM AUTHOR]

In 1975, P. Erdös proposed the problem of determining the maximum number f ( n ) of edges in a graph with n vertices in which any two cycles are of different lengths. In this paper, it is proved that f ( n ) ≥ n + 107 3 t + 7 3 for t = 1260 r + 169 ( r ≥ 1 ) and n ≥ 2119 4 t 2 + 87978 t + 15957 4 . Consequently, lim inf n → ∞ f ( n ) − n n ≥ 2 + 7654 19071 , which is better than the previous bounds 2 (Shi, 1988), 2 . 4 (Lai, 2003). The conjecture lim n → ∞ f ( n ) − n n = 2 . 4 is not true. [ABSTRACT FROM AUTHOR]

In the present paper, we compare the geometric–arithmetic index G A and the chromatic number χ of a connected graph with given order. We prove, among other results, an upper bound on the ratio G A ∕ χ . We also prove lower bounds on the chromatic number in terms of geometric–arithmetic index and number of vertices of a connected graph. The results obtained for the chromatic number χ are extended to the clique number ω . [ABSTRACT FROM AUTHOR]

A new explicit relationship between spanning trees and recurrent configurations of a graph is given by constructing subtree. Applying this relationship, we determine the total number of topplings in an avalanche. As applications, we calculate the sizes of avalanches of the Abelian sandpile model on the complete graph, the wheel and the complete bipartite graph. [ABSTRACT FROM AUTHOR]

We investigated covariational reasoning among 487 secondary mathematics teachers in the United States and South Korea. We presented an animation showing values of two varying magnitudes (v and u) on axes in a Cartesian plane along with a request that they sketch a graph of the value of u in relation to the value of v. We classified teachers ’ sketches on two independent criteria: (1) where they placed their initial point, and (2) their graph’s overall shape irrespective of initial point. There are distinct differences on both criteria between U.S. and South Korean teachers, suggesting that covariational reasoning is more prominent among South Korean secondary teachers than among U.S. secondary teachers. The results also suggest strongly that forming a multiplicative object that unites quantities ’ values is necessary to express covariation graphically. [ABSTRACT FROM AUTHOR]

In this paper, we study the relationship between the radius r and the attachment number a of a tetravalent graph admitting a half-arc-transitive group of automorphisms. These two parameters were first introduced in Marušič (1998), where among other things it was proved that a always divides 2 r . Intrigued by the empirical data from the census (Potočnik et al., 2015) of all such graphs of order up to 1000 we pose the question of whether all examples for which a does not divide r are arc-transitive. We prove that the answer to this question is positive in the case when a is twice an odd number. In addition, we completely characterise the tetravalent graphs admitting a half-arc-transitive group with r = 3 and a = 2 , and prove that they arise as non-sectional split 2 -fold covers of line graphs of 2 -arc-transitive cubic graphs. [ABSTRACT FROM AUTHOR]

Recently, the Chinese government raised an urban planning policy which suggests communities open their private roads for public transport and establish street networks with high spatial density in cities. In this context, the purpose of this study is to analyze the potential changes to street network accessibility using GIS techniques and to provide spatial information that may influence the decision making of urban managers. In addition to the existing street network data in the case study city, Shenzhen, intra-community roads are extracted from building footprints in GIS topographic database and used to construct a potential street network with respect to the community opening policy. An automatic GIS-based method is proposed here to analyze the location advantage information in the simulated urban environment, by combining Delaunay triangulation model and graph theory concepts. Specifically, we establish a two-step framework based on the spatial relationships between roads and buildings. Firstly, intra-community roads between neighboring building footprints are generated using a Delaunay triangulation skeleton model, and with the existing inter-community roads they form the simulated network. Secondly, street centrality indices of the current and simulated networks are compared in terms of closeness, betweenness and straightness. Results indicate that after applying the policy the global accessibility in the city would be increased at some places and decreased at others, and places' directness among others would be generally improved. In addition, the skeleton of central routes for through traffic would not change much. The presented method can also be applied to other cities. [ABSTRACT FROM AUTHOR]

By Berge's theorem, finding a maximum matching in a graph relies on the use of augmenting paths . When no further constraint is added, Edmonds' algorithm allows to compute a maximum matching in polynomial time by sequentially augmenting such paths. Motivated by applications in the scheduling of airline operations, we consider a similar problem where only paths of bounded length can be augmented. Precisely, let k ≥ 1 be an odd integer, and M a matching of a graph G . What is the maximum size of a matching that can be obtained from M by using only augmenting paths of length at most k ? We first prove that this problem can be solved in polynomial time for k ≤ 3 in any graph and that it is NP-complete for any fixed k ≥ 5 in the class of planar bipartite graphs of degree at most 3 and arbitrarily large girth. We then prove that this problem is in P, for any k , in several subclasses of trees such as caterpillars or trees with all vertices of degree at least 3 “far appart”. Moreover, this problem can be solved in time O ( n ) in the class of n -node trees when k and the maximum degree are fixed parameters. Finally, we consider a more constrained problem where only paths of length exactly k can be augmented. We prove that this latter problem becomes NP-complete for any fixed k ≥ 3 and in trees when k is part of the input. [ABSTRACT FROM AUTHOR]

Recently, it has been noticed that if the graph of an n-by-n complex matrix is a tree, then normality of the matrix is equivalent to three conditions, associated with the edges of the graph, that are much simpler than checking the standard definition of normality. Here, we characterize the precise class of graphs (much more general than trees), for which the three conditions are equivalent to normality, under a slight (and necessary) regularity condition. The graphs are those that are both triangle and 4-cycle free. For triangle-free graphs, normality implies absolute symmetry, under the same regularity condition. The results permit strong applications to real matrices, and to the notions of “principal normality”, and “essentially Hermitian”. [ABSTRACT FROM AUTHOR]