Log in

Relevant bibliographies by topics / Stable graph

Contents

Journal articles

Academic literature on the topic '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 lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.

Journal articles on the topic "Stable graph"

1

Abudayah, Mohammad, and Omar Alomari. "Semi Square Stable Graphs." Mathematics 7, no. 7 (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 (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 (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 (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 (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 (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 (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 (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 (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

More sources

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!