Log in

Relevant bibliographies by topics / Stable graph / Journal articles

Journal articles on the topic 'Stable graph'

To see the other types of publications on this topic, follow the link: Stable graph.

Author: Grafiati

Published: 14 March 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Stable graph.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Abudayah, Mohammad, and Omar Alomari. "Semi Square Stable Graphs." Mathematics 7, no. 7 (July 3, 2019): 597. http://dx.doi.org/10.3390/math7070597.

Full text

Abstract:

The independent number of a graph G is the cardinality of the maximum independent set of G, denoted by α ( G ) . The independent dominating number is the cardinality of the smallest independent set that dominates all vertices of G. In this paper, we introduce a new class of graphs called semi-square stable for which α ( G 2 ) = i ( G ) . We give a necessary and sufficient condition for a graph to be semi-square stable, and we study when interval graphs are semi-square stable.

APA, Harvard, Vancouver, ISO, and other styles

2

Wu, Pu, Huiqin Jiang, Sakineh Nazari-Moghaddam, Seyed Mahmoud Sheikholeslami, Zehui Shao, and Lutz Volkmann. "Independent Domination Stable Trees and Unicyclic Graphs." Mathematics 7, no. 9 (September 5, 2019): 820. http://dx.doi.org/10.3390/math7090820.

Full text

Abstract:

A set S ⊆ V ( G ) in a graph G is a dominating set if every vertex of G is either in S or adjacent to a vertex of S . A dominating set S is independent if any pair of vertices in S is not adjacent. The minimum cardinality of an independent dominating set on a graph G is called the independent domination number i ( G ) . A graph G is independent domination stable if the independent domination number of G remains unchanged under the removal of any vertex. In this paper, we study the basic properties of independent domination stable graphs, and we characterize all independent domination stable trees and unicyclic graphs. In addition, we establish bounds on the order of independent domination stable trees.

APA, Harvard, Vancouver, ISO, and other styles

3

Kayali, Moe, and Dan Suciu. "Quasi-Stable Coloring for Graph Compression." Proceedings of the VLDB Endowment 16, no. 4 (December 2022): 803–15. http://dx.doi.org/10.14778/3574245.3574264.

Full text

Abstract:

We propose quasi-stable coloring , an approximate version of stable coloring. Stable coloring, also called color refinement, is a well-studied technique in graph theory for classifying vertices, which can be used to build compact, lossless representations of graphs. However, its usefulness is limited due to its reliance on strict symmetries. Real data compresses very poorly using color refinement. We propose the first, to our knowledge, approximate color refinement scheme, which we call quasi-stable coloring. By using approximation, we alleviate the need for strict symmetry, and allow for a tradeoff between the degree of compression and the accuracy of the representation. We study three applications: Linear Programming, Max-Flow, and Betweenness Centrality, and provide theoretical evidence in each case that a quasi-stable coloring can lead to good approximations on the reduced graph. Next, we consider how to compute a maximal quasi-stable coloring: we prove that, in general, this problem is NP-hard, and propose a simple, yet effective algorithm based on heuristics. Finally, we evaluate experimentally the quasi-stable coloring technique on several real graphs and applications, comparing with prior approximation techniques.

APA, Harvard, Vancouver, ISO, and other styles

4

Liu, Ye. "On Chromatic Functors and Stable Partitions of Graphs." Canadian Mathematical Bulletin 60, no. 1 (March 1, 2017): 154–64. http://dx.doi.org/10.4153/cmb-2016-047-3.

Full text

Abstract:

AbstractThe chromatic functor of a simple graph is a functorization of the chromatic polynomial. M. Yoshinaga showed that two ûnite graphs have isomorphic chromatic functors if and only if they have the same chromatic polynomial. The key ingredient in the proof is the use of stable partitions of graphs. The latter is shown to be closely related to chromatic functors. In this note, we further investigate some interesting properties of chromatic functors associated with simple graphs using stable partitions. Our ûrst result is the determination of the group of natural automorphisms of the chromatic functor, which is, in general, a larger group than the automorphism group of the graph. The second result is that the composition of the chromatic functor associated with a ûnite graph restricted to the category FI of ûnite sets and injections with the free functor into the category of complex vector spaces yields a consistent sequence of representations of symmetric groups that is representation stable in the sense of Church–Farb.

APA, Harvard, Vancouver, ISO, and other styles

5

Osztényi, József. "A study of the neighborhood complex of $-stable Kneser graphs." Gradus 8, no. 3 (2021): 179–86. http://dx.doi.org/10.47833/2021.3.csc.006.

Full text

Abstract:

In 1978, Alexander Schrijver defined the stable Kneser graphs as a vertex critical subgraphs of the Kneser graphs. In the early 2000s, Günter M. Ziegler generalized Schrijver’s construction and defined the s-stable Kneser graphs. Thereafter Frédéric Meunier determined the chromatic number of the s-stable Kneser graphs for special cases and formulated a conjecture on the chromatic number of the s-stable Kneser graphs. In this paper we study a generalization of the s-stable Kneser graphs. For some specific values of the parameter we show that the neighborhood complex of < s, t >-stable Kneser graph has the same homotopy type as the (t − 1)-sphere. In particular, this implies that the chromatic number of this graph is t + 1.

APA, Harvard, Vancouver, ISO, and other styles

6

Tolue, Behnaz. "The stable subgroup graph." Boletim da Sociedade Paranaense de Matemática 36, no. 3 (July 1, 2018): 129–39. http://dx.doi.org/10.5269/bspm.v36i3.31678.

Full text

Abstract:

In this paper we introduce stable subgroup graph associated to the group $G$. It is a graph with vertex set all subgroups of $G$ and two distinct subgroups $H_1$ and $H_2$ are adjacent if $St_{G}(H_1)\cap H_2\neq 1$ or $St_{G}(H_2)\cap H_1\neq 1$. Its planarity is discussed whenever $G$ is an abelian group, $p$-group, nilpotent, supersoluble or soluble group. Finally, the induced subgraph of stable subgroup graph with vertex set whole non-normal subgroups is considered and its planarity is verified for some certain groups.

APA, Harvard, Vancouver, ISO, and other styles

7

Pask, David, Adam Sierakowski, and Aidan Sims. "Structure theory and stable rank for C*-algebras of finite higher-rank graphs." Proceedings of the Edinburgh Mathematical Society 64, no. 4 (October 4, 2021): 822–47. http://dx.doi.org/10.1017/s0013091521000626.

Full text

Abstract:

AbstractWe study the structure and compute the stable rank of $C^{*}$-algebras of finite higher-rank graphs. We completely determine the stable rank of the $C^{*}$-algebra when the $k$-graph either contains no cycle with an entrance or is cofinal. We also determine exactly which finite, locally convex $k$-graphs yield unital stably finite $C^{*}$-algebras. We give several examples to illustrate our results.

APA, Harvard, Vancouver, ISO, and other styles

8

Halevi, Yatir, Itay Kaplan, and Saharon Shelah. "Infinite stable graphs with large chromatic number." Transactions of the American Mathematical Society 375, no. 3 (December 21, 2021): 1767–99. http://dx.doi.org/10.1090/tran/8570.

Full text

Abstract:

We prove that if G = ( V , E ) G=(V,E) is an ω \omega -stable (respectively, superstable) graph with χ ( G ) > ℵ 0 \chi (G)>\aleph _0 (respectively, 2 ℵ 0 2^{\aleph _0} ) then G G contains all the finite subgraphs of the shift graph S h n ( ω ) \mathrm {Sh}_n(\omega ) for some n n . We prove a variant of this theorem for graphs interpretable in stationary stable theories. Furthermore, if G G is ω \omega -stable with U ⁡ ( G ) ≤ 2 \operatorname {U}(G)\leq 2 we prove that n ≤ 2 n\leq 2 suffices.

APA, Harvard, Vancouver, ISO, and other styles

9

Koh, Zhuan Khye, and Laura Sanità. "Stabilizing Weighted Graphs." Mathematics of Operations Research 45, no. 4 (November 2020): 1318–41. http://dx.doi.org/10.1287/moor.2019.1034.

Full text

Abstract:

An edge-weighted graph [Formula: see text] is called stable if the value of a maximum-weight matching equals the value of a maximum-weight fractional matching. Stable graphs play an important role in network bargaining games and cooperative matching games, because they characterize instances that admit stable outcomes. We give the first polynomial-time algorithm to find a minimum cardinality subset of vertices whose removal from G yields a stable graph, for any weighted graph G. The algorithm is combinatorial and exploits new structural properties of basic fractional matchings, which are of independent interest. In contrast, we show that the problem of finding a minimum cardinality subset of edges whose removal from a weighted graph G yields a stable graph, does not admit any constant-factor approximation algorithm, unless P = NP. In this setting, we develop an O(Δ)-approximation algorithm for the problem, where Δ is the maximum degree of a node in G.

APA, Harvard, Vancouver, ISO, and other styles

10

Jardine, J. F. "Stable Components and Layers." Canadian Mathematical Bulletin 63, no. 3 (October 23, 2019): 562–76. http://dx.doi.org/10.4153/s000843951900064x.

Full text

Abstract:

AbstractComponent graphs $\unicode[STIX]{x1D6E4}_{0}(F)$ are defined for arrays of sets $F$, and, in particular, for arrays of path components for Vietoris–Rips complexes and Lesnick complexes. The path components of $\unicode[STIX]{x1D6E4}_{0}(F)$ are the stable components of the array $F$. The stable components for the system of Lesnick complexes $\{L_{s,k}(X)\}$ for a finite data set $X$ decompose into layers, which are themselves path components of a graph. Combinatorial scoring functions are defined for layers and stable components.

APA, Harvard, Vancouver, ISO, and other styles

11

Matsuda, Kazunori, Hidefumi Ohsugi, and Kazuki Shibata. "Toric Rings and Ideals of Stable Set Polytopes." Mathematics 7, no. 7 (July 10, 2019): 613. http://dx.doi.org/10.3390/math7070613.

Full text

Abstract:

In the present paper, we study the normality of the toric rings of stable set polytopes, generators of toric ideals of stable set polytopes, and their Gröbner bases via the notion of edge polytopes of finite nonsimple graphs and the results on their toric ideals. In particular, we give a criterion for the normality of the toric ring of the stable set polytope and a graph-theoretical characterization of the set of generators of the toric ideal of the stable set polytope for a graph of stability number two. As an application, we provide an infinite family of stable set polytopes whose toric ideal is generated by quadratic binomials and has no quadratic Gröbner bases.

APA, Harvard, Vancouver, ISO, and other styles

12

Aref'ev, Roman D., John T. Baldwin, and Marco Mazzucco. "Classification of δ-invariant amalgamation classes." Journal of Symbolic Logic 64, no. 4 (December 1999): 1743–50. http://dx.doi.org/10.2307/2586809.

Full text

Abstract:

Hrushovski's generalization of the Fraisse construction has provided a rich source of examples in model theory, model theoretic algebra and random graph theory. The construction assigns to a dimension function δ and a class K of finite (finitely generated) models a countable ‘generic’ structure. We investigate here some of the simplest possible cases of this construction. The class K will be a class of finite graphs; the dimension, δ(A), of a finite graph A will be the cardinality of A minus the number of edges of A. Finally and significantly we restrict to classes which are δ-invariant. A class of finite graphs is δ-invariant if membership of a graph in the class is determined (as specified below) by the dimension and cardinality of the graph, and dimension and cardinality of all its subgraphs. Note that a generic graph constructed as in Hrushovski's example of a new strongly minimal set does not arise from a δ-invariant class.We show there are countably many δ-invariant (strong) amalgamation classes of finite graphs which are closed under subgraph and describe the countable generic models for these classes. This analysis provides ω-stable generic graphs with an array of saturation and model completeness properties which belies the similarity of their construction. In particular, we answer a question of Baizhanov (unpublished) and Baldwin [5] and show that this construction can yield an ω-stable generic which is not saturated. Further, we exhibit some ω-stable generic graphs that are not model complete.

APA, Harvard, Vancouver, ISO, and other styles

13

LI, YINKUI, ZONGTIAN WEI, XIAOKUI YUE, and ERQIANG LIU. "TENACITY OF TOTAL GRAPHS." International Journal of Foundations of Computer Science 25, no. 05 (August 2014): 553–62. http://dx.doi.org/10.1142/s012905411450021x.

Full text

Abstract:

Communication networks must be constructed to be as stable as possible, not only with the respect to the initial disruption, but also with respect to the possible reconstruction. Many graph theoretical parameters have been used to describe the stability of communication networks. Tenacity is a reasonable one, which shows not only the difficulty to break down the network but also the damage that has been caused. Total graphs are the largest graphs formed by the adjacent relations of elements of a graph. Thus, total graphs are highly recommended for the design of interconnection networks. In this paper, we determine the tenacity of the total graph of a path, cycle and complete bipartite graph, and thus give a lower bound of the tenacity for the total graph of a graph.

APA, Harvard, Vancouver, ISO, and other styles

14

Hammer, P. L., and A. K. Kelmans. "On Universal Threshold Graphs." Combinatorics, Probability and Computing 3, no. 3 (September 1994): 327–44. http://dx.doi.org/10.1017/s096354830000122x.

Full text

Abstract:

A graph G is threshold if there exists a ‘weight’ function w: V(G) → R such that the total weight of any stable set of G is less than the total weight of any non-stable set of G. Let n denote the set of threshold graphs with n vertices. A graph is called n-universal if it contains every threshold graph with n vertices as an induced subgraph. n-universal threshold graphs are of special interest, since they are precisely those n-universal graphs that do not contain any non-threshold induced subgraph.In this paper we shall study minimumn-universal (threshold) graphs, i.e.n-universal (threshold) graphs having the minimum number of vertices.It is shown that for any n ≥ 3 there exist minimum n-universal graphs, which are themselves threshold, and others which are not.Two extremal minimum n-universal graphs having respectively the minimum and the maximum number of edges are described, it is proved that they are unique, and that they are threshold graphs.The set of all minimum n-universal threshold graphs is then described constructively; it is shown that it forms a lattice isomorphic to the n − 1 dimensional Boolean cube, and that the minimum and the maximum elements of this lattice are the two extremal graphs introduced above.The proofs provide a (polynomial) recursive procedure that determines for any threshold graph G with n vertices and for any minimum n-universal threshold graph T, an induced subgraph G' of T isomorphic to G.

APA, Harvard, Vancouver, ISO, and other styles

15

Núñez, Marina, and Juan Vidal-Puga. "Stable cores in information graph games." Games and Economic Behavior 132 (March 2022): 353–67. http://dx.doi.org/10.1016/j.geb.2022.01.013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Domingos, Joao, and Jose M. F. Moura. "Graph Fourier Transform: A Stable Approximation." IEEE Transactions on Signal Processing 68 (2020): 4422–37. http://dx.doi.org/10.1109/tsp.2020.3009645.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Yang, Wenjie, Jianlin Zhang, Jingju Cai, and Zhiyong Xu. "Relation Selective Graph Convolutional Network for Skeleton-Based Action Recognition." Symmetry 13, no. 12 (November 30, 2021): 2275. http://dx.doi.org/10.3390/sym13122275.

Full text

Abstract:

Graph convolutional networks (GCNs) have made significant progress in the skeletal action recognition task. However, the graphs constructed by these methods are too densely connected, and the same graphs are used repeatedly among channels. Redundant connections will blur the useful interdependencies of joints, and the overly repetitive graphs among channels cannot handle changes in joint relations between different actions. In this work, we propose a novel relation selective graph convolutional network (RS-GCN). We also design a trainable relation selection mechanism. It encourages the model to choose solid edges to work and build a stable and sparse topology of joints. The channel-wise graph convolution and multiscale temporal convolution are proposed to strengthening the model’s representative power. Furthermore, we introduce an asymmetrical module named the spatial-temporal attention module for more stable context modeling. Combining those changes, our model achieves state-of-the-art performance on three public benchmarks, namely NTU-RGB+D, NTU-RGB+D 120, and Northwestern-UCLA.

APA, Harvard, Vancouver, ISO, and other styles

18

LEVIT, VADIM E., and EUGEN MANDRESCU. "Greedoids on vertex sets of B-joins of graphs." Carpathian Journal of Mathematics 30, no. 3 (2014): 335–44. http://dx.doi.org/10.37193/cjm.2014.03.10.

Full text

Abstract:

Let Ψ(G) be the family of all local maximum stable sets of graph G, i.e., S ∈ Ψ(G) if S is a maximum stable set of the subgraph induced by S ∪ N(S), where N(S) is the neighborhood of S. It was shown that Ψ(G) is a greedoid for every forest G [15]. The cases of bipartite graphs, triangle-free graphs, and well-covered graphs, were analyzed in [16, 17, 18, 19, 20, 24]. If G1, G2 are two disjoint graphs, and B is a bipartite graph having E(B) as an edge set and bipartition {V (G1), V (G2)}, then by B-join of G1, G2 we mean the graph B (G1, G2) whose vertex set is V (G1) ∪ V (G2) and edge set is E(G1) ∪ E(G2) ∪ E (B). In this paper we present several necessary and sufficient conditions for Ψ(B (G1, G2)) to form a greedoid, an antimatroid, and a matroid, in terms of Ψ(G1), Ψ(G2) and E (B).

APA, Harvard, Vancouver, ISO, and other styles

19

Su, Guifu, Guanbang Song, Jun Yin, and Junfeng Du. "A Complete Characterization of Bidegreed Split Graphs with Four Distinct α-Eigenvalues." Symmetry 14, no. 5 (April 28, 2022): 899. http://dx.doi.org/10.3390/sym14050899.

Full text

Abstract:

It is a well-known fact that a graph of diameter d has at least d+1 eigenvalues. A graph is d-extremal (resp. dα-extremal) if it has diameter d and exactly d+1 distinct eigenvalues (resp. α-eigenvalues), and a graph is split if its vertex set can be partitioned into a clique and a stable set. Such graphs have a diameter of at most three. If all vertex degrees in a split graph are either d˜ or d^, then we say it is (d˜,d^)-bidegreed. In this paper, we present a complete classification of the connected bidegreed 3α-extremal split graphs using the association of split graphs with combinatorial designs. This result is a natural generalization of Theorem 4.6 proved by Goldberg et al. and Proposition 3.8 proved by Song et al., respectively.

APA, Harvard, Vancouver, ISO, and other styles

20

SØRENSEN, ADAM P. W. "Geometric classification of simple graph algebras." Ergodic Theory and Dynamical Systems 33, no. 4 (July 5, 2012): 1199–220. http://dx.doi.org/10.1017/s0143385712000260.

Full text

Abstract:

AbstractInspired by Franks’ classification of irreducible shifts of finite type, we provide a short list of allowed moves on graphs that preserve the stable isomorphism class of the associated $C^*$-algebras. We show that if two graphs have stably isomorphic and simple unital algebras then we can use these moves to transform one into the other.

APA, Harvard, Vancouver, ISO, and other styles

21

LARKI, HOSSEIN, and ABDOLHAMID RIAZI. "STABLE RANK OF LEAVITT PATH ALGEBRAS OF ARBITRARY GRAPHS." Bulletin of the Australian Mathematical Society 88, no. 2 (December 12, 2012): 206–17. http://dx.doi.org/10.1017/s0004972712000913.

Full text

Abstract:

AbstractThe stable rank of Leavitt path algebras of row-finite graphs was computed by Ara and Pardo. In this paper we extend this to an arbitrary directed graph. In part our computation proceeds as for the row-finite case, but we also use knowledge of the row-finite setting by applying the desingularising method due to Drinen and Tomforde. In particular, we characterise purely infinite simple quotients of a Leavitt path algebra.

APA, Harvard, Vancouver, ISO, and other styles

22

Faizliev, Alexey, Vladimir Balash, Vladimir Petrov, Alexey Grigoriev, Dmitriy Melnichuk, and Sergei Sidorov. "Stability Analysis of Company Co-Mention Network and Market Graph Over Time Using Graph Similarity Measures." Journal of Open Innovation: Technology, Market, and Complexity 5, no. 3 (August 10, 2019): 55. http://dx.doi.org/10.3390/joitmc5030055.

Full text

Abstract:

The aim of the paper is to provide an analysis of news and financial data using their network representation. The formation of network structures from data sources is carried out using two different approaches: by building the so-called market graph in which nodes represent financial assets (e.g., stocks) and the edges between nodes stand for the correlation between the corresponding assets, by constructing a company co-mention network in which any two companies are connected by an edge if a news item mentioning both companies has been published in a certain period of time. Topological changes of the networks over the period 2005–2010 are investigated using the sliding window of six-month duration. We study the stability of the market graph and the company co-mention network over time and establish which of the two networks was more stable during the period. In addition, we examine the impact of the crisis of 2008 on the stability of the market graph as well as the company co-mention network. The networks that are considered in this paper and that are the objects of our study (the market graph and the company co-mention network) have a non-changing set of nodes (companies), and can change over time by adding/removing links between these nodes. Different graph similarity measures are used to evaluate these changes. If a network is stable over time, a measure of similarity between two graphs constructed for two different time windows should be close to zero. If there was a sharp change between the graphs constructed for two adjacent periods, then this should lead to a sharp increase in the value of the similarity measure between these two graphs. This paper uses the graph similarity measures which were proposed relatively recently. In addition, to estimate how the networks evolve over time we exploit QAP (Quadratic Assignment Procedure). While there is a sufficient amount of works studying the dynamics of graphs (including the use of graph similarity metrics), in this paper the company co-mention network dynamics is examined both individually and in comparison with the dynamics of market graphs for the first time.

APA, Harvard, Vancouver, ISO, and other styles

23

Ahmad, Eman Camad, Gina Alquiza Malacas, and Sergio Jr Rosales Canoy. "Stable Locating-Dominating Sets in Graphs." European Journal of Pure and Applied Mathematics 14, no. 3 (August 5, 2021): 638–49. http://dx.doi.org/10.29020/nybg.ejpam.v14i3.3998.

Full text

Abstract:

A set S âŠ† V(G) of a (simple) undirected graph G is a locating-dominating set of G if for each v âˆˆ V(G) \ S, there exists w âˆˆ S such tha vw âˆˆ E(G) and NG(x) âˆ© S= NG(y)âˆ©S for any distinct vertices x and y in V(G) \ S. S is a stable locating-dominating set of G if it is a locating-dominating set of G and S \ {v} is a locating-dominating set of G for each v âˆˆ S. The minimum cardinality of a stable locating-dominating set of G, denoted by Î³sl(G), is called the stable locating-domination number of G. In this paper, we investigate this concept and the corresponding parameter for some graphs. Further, we introduce other related concepts and use them to characterize the stable locating-dominating sets in some graphs.

APA, Harvard, Vancouver, ISO, and other styles

24

Fuchs, Mathias, and Kaspar Riesen. "A novel way to formalize stable graph cores by using matching-graphs." Pattern Recognition 131 (November 2022): 108846. http://dx.doi.org/10.1016/j.patcog.2022.108846.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Reckwerdt, Eric. "Weak amenability is stable under graph products." Journal of the London Mathematical Society 96, no. 1 (June 26, 2017): 133–55. http://dx.doi.org/10.1112/jlms.12054.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Mennens, Robin J. P., Roeland Scheepens, and Michel A. Westenberg. "A stable graph layout algorithm for processes." Computer Graphics Forum 38, no. 3 (June 2019): 725–37. http://dx.doi.org/10.1111/cgf.13723.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Prue, Paul, and Travis Scrimshaw. "Abrams's stable equivalence for graph braid groups." Topology and its Applications 178 (December 2014): 136–45. http://dx.doi.org/10.1016/j.topol.2014.09.009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Wang, Yunzhe, George Baciu, and Chenhui Li. "A Layout-Based Classification Method for Visualizing Time-Varying Graphs." ACM Transactions on Knowledge Discovery from Data 15, no. 4 (June 2021): 1–24. http://dx.doi.org/10.1145/3441301.

Full text

Abstract:

Connectivity analysis between the components of large evolving systems can reveal significant patterns of interaction. The systems can be simulated by topological graph structures. However, such analysis becomes challenging on large and complex graphs. Tasks such as comparing, searching, and summarizing structures, are difficult due to the enormous number of calculations required. For time-varying graphs, the temporal dimension even intensifies the difficulty. In this article, we propose to reduce the complexity of analysis by focusing on subgraphs that are induced by closely related entities. To summarize the diverse structures of subgraphs, we build a supervised layout-based classification model. The main premise is that the graph structures can induce a unique appearance of the layout. In contrast to traditional graph theory-based and contemporary neural network-based methods of graph classification, our approach generates low costs and there is no need to learn informative graph representations. Combined with temporally stable visualizations, we can also facilitate the understanding of sub-structures and the tracking of graph evolution. The method is evaluated on two real-world datasets. The results show that our system is highly effective in carrying out visual-based analytics of large graphs.

APA, Harvard, Vancouver, ISO, and other styles

29

Manimekalai, S., and U. Mary. "Various Characteristics of a Few Topological Indices for γ_Stable Graphs." International Journal of Engineering & Technology 7, no. 4.10 (October 2, 2018): 925. http://dx.doi.org/10.14419/ijet.v7i4.10.26628.

Full text

Abstract:

In this manuscript we have given various characteristics of some topological indices for γ stable graphs and computation of Wiener index using python program for Complex graph structures which frequently appear in all chemical Structure.

APA, Harvard, Vancouver, ISO, and other styles

30

LEVIT, VADIM E., and EUGEN MANDRESCU. "VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS." Discrete Mathematics, Algorithms and Applications 03, no. 02 (June 2011): 245–52. http://dx.doi.org/10.1142/s1793830911001115.

Full text

Abstract:

A maximum stable set in a graph G is a stable set of maximum cardinality. S is a local maximum stable set of G, and we write S ∈ Ψ(G), if S is a maximum stable set of the subgraph induced by S ∪ N(S), where N(S) is the neighborhood of S. Nemhauser and Trotter Jr. [Vertex packings: structural properties and algorithms, Math. Program.8 (1975) 232–248], proved that any S ∈ Ψ(G) is a subset of a maximum stable set of G. In [Levit and Mandrescu, A new greedoid: the family of local maximum stable sets of a forest, Discrete Appl. Math.124 (2002) 91–101] we have shown that the family Ψ(T) of a forest T forms a greedoid on its vertex set. The cases where G is bipartite, triangle-free, well-covered, while Ψ(G) is a greedoid, were analyzed in [Levit and Mandrescu, Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings, Discrete Appl. Math.132 (2004) 163–174], [Levit and Mandrescu, Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids, Discrete Appl. Math.155 (2007) 2414–2425], [Levit and Mandrescu, Well-covered graphs and greedoids, Proc. 14th Computing: The Australasian Theory Symp. (CATS2008), Wollongong, NSW, Conferences in Research and Practice in Information Technology, Vol. 77 (2008) 89–94], respectively. In this paper we demonstrate that if G is a very well-covered graph of girth ≥4, then the family Ψ(G) is a greedoid if and only if G has a unique perfect matching.

APA, Harvard, Vancouver, ISO, and other styles

31

Ahmed Mouhamadou WADE. "Tight bounds on exploration of constantly connected cacti-paths." World Journal of Advanced Research and Reviews 12, no. 1 (October 30, 2021): 355–61. http://dx.doi.org/10.30574/wjarr.2021.12.1.0534.

Full text

Abstract:

In this paper, we study the necessary and sufficient time to explore constantly connected dynamics graphs by a mobile entity (agent). A dynamic graph is constantly connected if for each time units, there exists a stable connected spanning tree [10]. We focus on the case where the underlying graph is a cactus-path (graph reduced to a path of k rings in which two neighbor rings have at most one vertex in common) and we assume that the agent knows the dynamics of the graph. We show that 5n - Θ(1) time units are necessary and sufficient to explore any constantly connected dynamic graph based on the cactus-path 〖Ch〗_(2,n) (composed of two same size ringsn). The upper bound is generalized on dynamic graphs based on cacti-paths with k rings. We show that for any constantly connected dynamic graph of size N based on a cactus-path, 4N -max{n_1,n_k} -3k -3 time units are sufficient to explore the graph, with k the length of the path, N=∑_(i=1)^k▒n_i -k+1 the size of the dynamic graph and n_i the size of the ring which is at position i starting from left to right.

APA, Harvard, Vancouver, ISO, and other styles

32

Eilers, Søren, Gunnar Restorff, Efren Ruiz, and Adam P. W. Sørensen. "Geometric Classification of Graph C*-algebras over Finite Graphs." Canadian Journal of Mathematics 70, no. 2 (April 1, 2018): 294–353. http://dx.doi.org/10.4153/cjm-2017-016-7.

Full text

Abstract:

AbstractWe address the classification problem for graph C*-algebras of finite graphs (finitely many edges and vertices), containing the class of Cuntz-Krieger algebras as a prominent special case. Contrasting earlier work, we do not assume that the graphs satisfy the standard condition (K), so that the graph C*-algebras may come with uncountably many ideals.We find that in this generality, stable isomorphism of graph C*-algebras does not coincide with the geometric notion of Cuntz move equivalence. However, adding a modest condition on the graphs, the two notions are proved to be mutually equivalent and equivalent to the C*-algebras having isomorphicK-theories. This proves in turn that under this condition, the graph C*-algebras are in fact classifiable byK-theory, providing, in particular, complete classification when the C* - algebras in question are either of real rank zero or type I/postliminal. The key ingredient in obtaining these results is a characterization of Cuntz move equivalence using the adjacency matrices of the graphs.Our results are applied to discuss the classification problem for the quantumlens spaces defined by Hong and Szymański, and to complete the classification of graph C*-algebras associated with all simple graphs with four vertices or less.

APA, Harvard, Vancouver, ISO, and other styles

33

Boliac, Rodica, and Vadim V. Lozin. "An augmenting graph approach to the stable set problem in P5-free graphs." Discrete Applied Mathematics 131, no. 3 (September 2003): 567–75. http://dx.doi.org/10.1016/s0166-218x(03)00221-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Bilò, Vittorio, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli. "Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation." Journal of Artificial Intelligence Research 62 (June 21, 2018): 315–71. http://dx.doi.org/10.1613/jair.1.11211.

Full text

Abstract:

We consider fractional hedonic games, a subclass of coalition formation games that can be succinctly modeled by means of a graph in which nodes represent agents and edge weights the degree of preference of the corresponding endpoints. The happiness or utility of an agent for being in a coalition is the average value she ascribes to its members. We adopt Nash stable outcomes as the target solution concept; that is we focus on states in which no agent can improve her utility by unilaterally changing her own group. We provide existence, efficiency and complexity results for games played on both general and specific graph topologies. As to the efficiency results, we mainly study the quality of the best Nash stable outcome and refer to the ratio between the social welfare of an optimal coalition structure and the one of such an equilibrium as to the price of stability. In this respect, we remark that a best Nash stable outcome has a natural meaning of stability, since it is the optimal solution among the ones which can be accepted by selfish agents. We provide upper and lower bounds on the price of stability for different topologies, both in case of weighted and unweighted edges. Beside the results for general graphs, we give refined bounds for various specific cases, such as triangle-free, bipartite graphs and tree graphs. For these families, we also show how to efficiently compute Nash stable outcomes with provable good social welfare.

APA, Harvard, Vancouver, ISO, and other styles

35

Yue, Jumei, Yongyi Yan, and He Deng. "Matrix Approach to Formulate and Search k-ESS of Graphs Using the STP Theory." Journal of Mathematics 2021 (July 6, 2021): 1–12. http://dx.doi.org/10.1155/2021/7230661.

Full text

Abstract:

In this paper, the structure of graphs in terms of k-externally stable set (k-ESS) is investigated by a matrix method based on a new matrix product, called semitensor product of matrices. By defining an eigenvector and an eigenvalue of the node subset of a graph, three necessary and sufficient conditions of k-ESS, minimum k-ESS, and k-kernels of graphs are proposed in a matrix form, respectively. Using these conditions, the concepts of k-ESS matrix, minimum k-ESS matrix, and k-kernel matrix are introduced. These matrices provide complete information of the corresponding structures of a graph. Further, three algorithms are designed, respectively, to find all these three structures of a graph by conducting a series of matrix operation. Finally, the correctness and effectiveness of the results are checked by studying an example. The proposed method and results may offer a new way to investigate the problems related to graph structures in the field of network systems.

APA, Harvard, Vancouver, ISO, and other styles

36

Matsuda, Hiroyuki, and Toshiyuki Namba. "Food Web Graph of a Coevolutionarily Stable Community." Ecology 72, no. 1 (February 1991): 267–76. http://dx.doi.org/10.2307/1938920.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Talmaciu, Mihai, and Elena Nechita. "On Polar, Trivially Perfect Graphs." International Journal of Computers Communications & Control 5, no. 5 (December 1, 2010): 939. http://dx.doi.org/10.15837/ijccc.2010.5.2257.

Full text

Abstract:

<p>During the last decades, different types of decompositions have been processed in the field of graph theory. In various problems, for example in the construction of recognition algorithms, frequently appears the so-called weakly decomposition of graphs.<br />Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. Recognizing a polar graph is known to be NP-complete. For this class of graphs, polynomial algorithms for the maximum stable set problem are unknown and algorithms for the dominating set problem are also NP-complete.<br />In this paper we characterize the polar graphs using the weakly decomposition, give a polynomial time algorithm for recognizing graphs that are both trivially perfect and polar, and directly calculate the domination number. For the stability number and clique number, we give polynomial time algorithms. </p>

APA, Harvard, Vancouver, ISO, and other styles

38

Caspers, Martijn. "Connes embeddability of graph products." Infinite Dimensional Analysis, Quantum Probability and Related Topics 19, no. 01 (March 2016): 1650004. http://dx.doi.org/10.1142/s0219025716500041.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Igarashi, Ayumi, Jakub Sliwinski, and Yair Zick. "Forming Probably Stable Communities with Limited Interactions." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 2053–60. http://dx.doi.org/10.1609/aaai.v33i01.33012053.

Full text

Abstract:

A community needs to be partitioned into disjoint groups; each community member has an underlying preference over the groups that they would want to be a member of. We are interested in finding a stable community structure: one where no subset of members S wants to deviate from the current structure. We model this setting as a hedonic game, where players are connected by an underlying interaction network, and can only consider joining groups that are connected subgraphs of the underlying graph. We analyze the relation between network structure, and one’s capability to infer statistically stable (also known as PAC stable) player partitions from data. We show that when the interaction network is a forest, one can efficiently infer PAC stable coalition structures. Furthermore, when the underlying interaction graph is not a forest, efficient PAC stabilizability is no longer achievable. Thus, our results completely characterize when one can leverage the underlying graph structure in order to compute PAC stable outcomes for hedonic games. Finally, given an unknown underlying interaction network, we show that it is NP-hard to decide whether there exists a forest consistent with data samples from the network.

APA, Harvard, Vancouver, ISO, and other styles

40

LOERA, J. A., J. LEE, S. MARGULIES, and S. ONN. "Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz." Combinatorics, Probability and Computing 18, no. 4 (July 2009): 551–82. http://dx.doi.org/10.1017/s0963548309009894.

Full text

Abstract:

Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colourable, Hamiltonian, etc.) if and only if a related system of polynomial equations has a solution.For an infeasible polynomial system, the (complex) Hilbert Nullstellensatz gives a certificate that the associated combinatorial problem is infeasible. Thus, unless P = NP, there must exist an infinite sequence of infeasible instances of each hard combinatorial problem for which the minimum degree of a Hilbert Nullstellensatz certificate of the associated polynomial system grows.In the first part of the paper, we show that the minimum degree of a Nullstellensatz certificate for the non-existence of a stable set of size greater than the stability number of the graph is the stability number of the graph. Moreover, such a certificate contains at least one term per stable set of G. In contrast, for non-3-colourability, we proved that the minimum degree of a Nullstellensatz certificate is at least four. Our efforts so far have only yielded graphs with Nullstellensatz certificates of precisely that degree.In the second part of this paper, for the purpose of computation, we construct new polynomial encodings for the problems of finding in a graph its longest cycle, the largest planar subgraph, the edge-chromatic number, or the largest k-colourable subgraph. We include some applications to graph theory.

APA, Harvard, Vancouver, ISO, and other styles

41

WILDS, ROY, and LEON GLASS. "AN ATLAS OF ROBUST, STABLE, HIGH-DIMENSIONAL LIMIT CYCLES." International Journal of Bifurcation and Chaos 19, no. 12 (December 2009): 4055–96. http://dx.doi.org/10.1142/s0218127409025225.

Full text

Abstract:

We present a method for constructing dynamical systems with robust, stable limit cycles in arbitrary dimensions. Our approach is based on a correspondence between dynamics in a class of differential equations and directed graphs on the n-dimensional hypercube (n-cube). When the directed graph contains a certain type of cycle, called a cyclic attractor, then a stable limit cycle solution of the differential equations exists. A novel method for constructing regulatory systems that we call minimal regulatory networks from directed graphs facilitates investigation of limit cycles in arbitrarily high dimensions. We identify two families of cyclic attractors that are present for all dimensions n ≥ 3: cyclic negative feedback and sequential disinhibition. For each, we obtain explicit representations for the differential equations in arbitrary dimension. We also provide a complete listing of minimal regulatory networks, a representative differential equation, and a bifurcation analysis for each cyclic attractor in dimensions 3–5. This work joins discrete concepts of symmetry and classification with analysis of differential equations useful for understanding dynamics in complex biological control networks.

APA, Harvard, Vancouver, ISO, and other styles

42

Vandaele, Robin, Bastian Rieck, Yvan Saeys, and Tijl De Bie. "Stable topological signatures for metric trees through graph approximations." Pattern Recognition Letters 147 (July 2021): 85–92. http://dx.doi.org/10.1016/j.patrec.2021.03.035.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Jeong, J. A., G. H. Park, and D. Y. Shin. "Stable rank and real rank of graph C∗-algebras." Pacific Journal of Mathematics 200, no. 2 (October 1, 2001): 331–43. http://dx.doi.org/10.2140/pjm.2001.200.331.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Chapuy, G., and G. Perarnau. "Local Convergence and Stability of Tight Bridge-addable Classes." Canadian Journal of Mathematics 72, no. 3 (October 15, 2018): 563–601. http://dx.doi.org/10.4153/s0008414x18000020.

Full text

Abstract:

AbstractA class of graphs is bridge-addable if given a graph $G$ in the class, any graph obtained by adding an edge between two connected components of $G$ is also in the class. The authors recently proved a conjecture of McDiarmid, Steger, and Welsh stating that if ${\mathcal{G}}$ is bridge-addable and $G_{n}$ is a uniform $n$-vertex graph from ${\mathcal{G}}$, then $G_{n}$ is connected with probability at least $(1+o_{n}(1))e^{-1/2}$. The constant $e^{-1/2}$ is best possible, since it is reached for the class of all forests.In this paper, we prove a form of uniqueness in this statement: if ${\mathcal{G}}$ is a bridge-addable class and the random graph $G_{n}$ is connected with probability close to $e^{-1/2}$, then $G_{n}$ is asymptotically close to a uniform $n$-vertex random forest in a local sense. For example, if the probability converges to $e^{-1/2}$, then $G_{n}$ converges in the sense of Benjamini–Schramm to the uniformly infinite random forest $F_{\infty }$. This result is reminiscent of so-called “stability results” in extremal graph theory, the difference being that here the stable extremum is not a graph but a graph class.

APA, Harvard, Vancouver, ISO, and other styles

45

Welling, Max, and Yee Whye Teh. "Linear Response Algorithms for Approximate Inference in Graphical Models." Neural Computation 16, no. 1 (January 1, 2004): 197–221. http://dx.doi.org/10.1162/08997660460734056.

Full text

Abstract:

Belief propagation (BP) on cyclic graphs is an efficient algorithm for computing approximate marginal probability distributions over single nodes and neighboring nodes in the graph. However, it does not prescribe a way to compute joint distributions over pairs of distant nodes in the graph. In this article, we propose two new algorithms for approximating these pairwise probabilities, based on the linear response theorem. The first is a propagation algorithm that is shown to converge if BP converges to a stable fixed point. The second algorithm is based on matrix inversion. Applying these ideas to gaussian random fields, we derive a propagation algorithm for computing the inverse of a matrix.

APA, Harvard, Vancouver, ISO, and other styles

46

S, Purushothama. "Critical and stable pendant domination." Open Journal of Mathematical Sciences 6, no. 1 (June 21, 2022): 187–91. http://dx.doi.org/10.30538/oms2022.0187.

Full text

Abstract:

Let \(S\) be a dominating set of a graph \(G\). The set \(S\) is called a pendant dominating set of \(G\) if the induced subgraph of \(S\) contains a minimum of one node of degree one. The minimum cardinality of the pendant dominating set in \(G\) is referred to as the pendant domination number of \(G\), indicated by \(\gamma_{pe}(G)\). This article analyzes the effect of \(\gamma_{pe}(G)\) when an arbitrary node or edge is removed.

APA, Harvard, Vancouver, ISO, and other styles

47

Pu, Shilin, Liang Chu, Jincheng Hu, Shibo Li, Jihao Li, and Wen Sun. "SGGformer: Shifted Graph Convolutional Graph-Transformer for Traffic Prediction." Sensors 22, no. 22 (November 21, 2022): 9024. http://dx.doi.org/10.3390/s22229024.

Full text

Abstract:

Accurate traffic prediction is significant in intelligent cities’ safe and stable development. However, due to the complex spatiotemporal correlation of traffic flow data, establishing an accurate traffic prediction model is still challenging. Aiming to meet the challenge, this paper proposes SGGformer, an advanced traffic grade prediction model which combines a shifted window operation, a multi-channel graph convolution network, and a graph Transformer network. Firstly, the shifted window operation is used for coarsening the time series data, thus, the computational complexity can be reduced. Then, a multi-channel graph convolutional network is adopted to capture and aggregate the spatial correlations of the roads in multiple dimensions. Finally, the improved graph Transformer based on the advanced Transformer model is proposed to extract the long-term temporal correlation of traffic data effectively. The prediction performance is evaluated by using actual traffic datasets, and the test results show that the SGGformer proposed exceeds the state-of-the-art baseline.

APA, Harvard, Vancouver, ISO, and other styles

48

Eilers, Søren, Gunnar Restorff, and Efren Ruiz. "The Ordered K-theory of a Full Extension." Canadian Journal of Mathematics 66, no. 3 (June 1, 2014): 596–624. http://dx.doi.org/10.4153/cjm-2013-015-7.

Full text

Abstract:

AbstractLet be a C*-algebra with real rank zero that has the stable weak cancellation property. Let be an ideal of such that is stable and satisfies the corona factorization property. We prove thatis a full extension if and only if the extension is stenotic and K-lexicographic. As an immediate application, we extend the classification result for graph C*-algebras obtained by Tomforde and the first named author to the general non-unital case. In combination with recent results by Katsura, Tomforde, West, and the first named author, our result may also be used to give a purely K-theoretical description of when an essential extension of two simple and stable graph C*-algebras is again a graph C*- algebra.

APA, Harvard, Vancouver, ISO, and other styles

49

Ivakin, Y., and S. Potapichev. "ALGORITHM OF BIOGRAPHICAL HYPOTHESES TESTING BASED ON GEOCHRONOLOGICAL TRACKING." Telecom IT 7, no. 1 (2019): 60–74. http://dx.doi.org/10.31854/2307-1303-2019-7-1-60-74.

Full text

Abstract:

Research subject. Information technology of the geochronological tracking is an assembly of processes that accumulate and integrate data about geographic relocation of historical figures for a given time interval and represent the results as a generalizing graph in GIS. Method. Hypotheses on the stable tendencies in migration could be represented as the above graph’s sub-graphs. Such tendencies testing would be reduced to the search and evaluation of the statistical significance for the matching graphs’ isomorphism. Full-featured development of computer interpretation of the graph theory methods based on geochronological tracking provides new quality of historical research using modern GIS-tools. Practical relevance. Namely, researcher can use the quantitative methods of the corresponding logical-analytical apparatus. The proposed paper deals with a consideration of qualitatively new possibilities of such an approach and the corresponding algorithmic apparatus.

APA, Harvard, Vancouver, ISO, and other styles

50

Zhang, Dehai, Xiaobo Yang, Linan Liu, and Qing Liu. "A Knowledge Graph-Enhanced Attention Aggregation Network for Making Recommendations." Applied Sciences 11, no. 21 (November 5, 2021): 10432. http://dx.doi.org/10.3390/app112110432.

Full text

Abstract:

In recent years, many researchers have devoted time to designing algorithms used to introduce external information from knowledge graphs, to solve the problems of data sparseness and the cold start, and thus improve the performance of recommendation systems. Inspired by these studies, we proposed KANR, a knowledge graph-enhanced attention aggregation network for making recommendations. This is an end-to-end deep learning model using knowledge graph embedding to enhance the attention aggregation network for making recommendations. It consists of three main parts. The first is the attention aggregation network, which collect the user’s interaction history and captures the user’s preference for each item. The second is the knowledge graph-embedded model, which aims to integrate the knowledge. The semantic information of the nodes and edges in the graph is mapped to the low-dimensional vector space. The final part is the information interaction unit, which is used for fusing the features of two vectors. Experiments showed that our model achieved a stable improvement compared to the baseline model in making recommendations for movies, books, and music.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!