13 results on '"Independence number"'
Search Results
2. On the Independence Number of Cayley Digraphs of Clifford Semigroups.
- Author
-
Limkul, Krittawit and Panma, Sayan
- Subjects
- *
CAYLEY graphs , *INDEPENDENT sets - Abstract
Let S be a Clifford semigroup and A a subset of S. We write C a y (S , A) for the Cayley digraph of a Clifford semigroup S relative to A. The (weak, path, weak path) independence number of a graph is the maximum cardinality of an (weakly, path, weakly path) independent set of vertices in the graph. In this paper, we characterize maximal connected subdigraphs of C a y (S , A) and apply these results to determine the (weak, path, weak path) independence number of C a y (S , A) . [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
3. Spanning k -Ended Tree in 2-Connected Graph.
- Author
-
Lei, Wanpeng and Yin, Jun
- Subjects
- *
TREE graphs , *SPANNING trees , *INDEPENDENT sets , *GRAPH connectivity - Abstract
Win proved a very famous conclusion that states the graph G with connectivity κ (G) , independence number α (G) and α (G) ≤ κ (G) + k − 1 (k ≥ 2) contains a spanning k-ended tree. This means that there exists a spanning tree with at most k leaves. In this paper, we strengthen the Win theorem to the following: Let G be a simple 2-connected graph such that | V (G) | ≥ 2 κ (G) + k , α (G) ≤ κ (G) + k (k ≥ 2) and the number of maximum independent sets of cardinality κ + k is at most n − 2 κ − k + 1 . Then, either G contains a spanning k-ended tree or a subgraph of K κ ∨ ((k + κ − 1) K 1 ∪ K n − 2 κ − k + 1) . [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
4. On Trees with Given Independence Numbers with Maximum Gourava Indices.
- Author
-
Wang, Ying, Aslam, Adnan, Idrees, Nazeran, Kanwal, Salma, Iram, Nabeela, and Razzaque, Asima
- Subjects
- *
MOLECULAR connectivity index , *MOLECULAR graphs , *REAL numbers , *ISOMORPHISM (Mathematics) , *STRUCTURE-activity relationships , *INDEPENDENT sets , *TOPOLOGICAL degree - Abstract
In mathematical chemistry, molecular descriptors serve an important role, primarily in quantitative structure–property relationship (QSPR) and quantitative structure–activity relationship (QSAR) studies. A topological index of a molecular graph is a real number that is invariant under graph isomorphism conditions and provides information about its size, symmetry, degree of branching, and cyclicity. For any graph N, the first and second Gourava indices are defined as G O 1 (N) = ∑ u ′ v ′ ∈ E (N) (d (u ′) + d (v ′) + d (u ′) d (v ′) ) and G O 2 (N) = ∑ u ′ v ′ ∈ E (N) (d (u ′) + d (v ′)) d (u ′) d (v ′) , respectively.The independence number of a graph N, being the cardinality of its maximal independent set, plays a vital role in reading the energies of chemical trees. In this research paper, it is shown that among the family of trees of order δ and independence number ξ , the spur tree denoted as Υ δ , ξ maximizes both 1st and 2nd Gourava indices, and with these characterizations this graph is unique. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. General Properties on Differential Sets of a Graph.
- Author
-
Basilio, Ludwin A., Bermudo, Sergio, Hernández-Gómez, Juan C., and Sigarreta, José M.
- Subjects
- *
GENERALIZATION , *MOTIVATION (Psychology) , *MAXIMA & minima - Abstract
Let G = (V , E) be a graph, and let β ∈ R . Motivated by a service coverage maximization problem with limited resources, we study the β -differential of G. The β-differential of G, denoted by ∂ β (G) , is defined as ∂ β (G) : = max { | B (S) | − β | S | s u c h t h a t S ⊆ V } . The case in which β = 1 is known as the differential of G, and hence ∂ β (G) can be considered as a generalization of the differential ∂ (G) of G. In this paper, upper and lower bounds for ∂ β (G) are given in terms of its order | G | , minimum degree δ (G) , maximum degree Δ (G) , among other invariants of G. Likewise, the β -differential for graphs with heavy vertices is studied, extending the set of applications that this concept can have. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
6. Common Independence in Graphs.
- Author
-
Dettlaff, Magda, Lemańska, Magdalena, and Topp, Jerzy
- Subjects
- *
DOMINATING set , *INDEPENDENT sets , *INTEGERS - Abstract
The cardinality of a largest independent set of G, denoted by α (G) , is called the independence number of G. The independent domination number i (G) of a graph G is the cardinality of a smallest independent dominating set of G. We introduce the concept of the common independence number of a graph G, denoted by α c (G) , as the greatest integer r such that every vertex of G belongs to some independent subset X of V G with | X | ≥ r . The common independence number α c (G) of G is the limit of symmetry in G with respect to the fact that each vertex of G belongs to an independent set of cardinality α c (G) in G, and there are vertices in G that do not belong to any larger independent set in G. For any graph G, the relations between above parameters are given by the chain of inequalities i (G) ≤ α c (G) ≤ α (G) . In this paper, we characterize the trees T for which i (T) = α c (T) , and the block graphs G for which α c (G) = α (G) . [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
7. Graphs with Minimal Strength.
- Author
-
Gao, Zhenbin, Lau, Gee-Choon, Shiu, Wai-Chee, Semaničová-Feňovčíková, Andrea, and Bača, Martin
- Subjects
- *
PROBLEM solving - Abstract
For any graph G of order p, a bijection f : V (G) → { 1 , 2 , ... , p } is called a numbering of G. The strength s t r f (G) of a numbering f of G is defined by s t r f (G) = max { f (u) + f (v) | u v ∈ E (G) } , and the strength s t r (G) of a graph G is s t r (G) = min { s t r f (G) | f is a numbering of G }. In this paper, many open problems are solved, and the strengths of new families of graphs are determined. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
8. On Sombor Index.
- Author
-
Das, Kinkar Chandra, Çevik, Ahmet Sinan, Cangul, Ismail Naci, and Shang, Yilun
- Subjects
- *
MOLECULAR connectivity index , *MOLECULAR graphs - Abstract
The concept of Sombor index (S O) was recently introduced by Gutman in the chemical graph theory. It is a vertex-degree-based topological index and is denoted by Sombor index S O : S O = S O (G) = ∑ v i v j ∈ E (G) d G (v i) 2 + d G (v j) 2 , where d G (v i) is the degree of vertex v i in G. Here, we present novel lower and upper bounds on the Sombor index of graphs by using some graph parameters. Moreover, we obtain several relations on Sombor index with the first and second Zagreb indices of graphs. Finally, we give some conclusions and propose future work. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
9. New Bounds for the α -Indices of Graphs.
- Author
-
Lenes, Eber, Mallea-Zepeda, Exequiel, and Rodríguez, Jonnathan
- Subjects
- *
MATRICES (Mathematics) , *EDGES (Geometry) - Abstract
Let G be a graph, for any real 0 ≤ α ≤ 1 , Nikiforov defines the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G) , where A (G) and D (G) are the adjacency matrix and diagonal matrix of degrees of the vertices of G. This paper presents some extremal results about the spectral radius ρ α (G) of the matrix A α (G) . In particular, we give a lower bound on the spectral radius ρ α (G) in terms of order and independence number. In addition, we obtain an upper bound for the spectral radius ρ α (G) in terms of order and minimal degree. Furthermore, for n > l > 0 and 1 ≤ p ≤ ⌊ n − l 2 ⌋ , let G p ≅ K l ∨ (K p ∪ K n − p − l) be the graph obtained from the graphs K l and K p ∪ K n − p − l and edges connecting each vertex of K l with every vertex of K p ∪ K n − p − l. We prove that ρ α (G p + 1) < ρ α (G p) for 1 ≤ p ≤ ⌊ n − l 2 ⌋ − 1 . [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
10. On the Secure Total Domination Number of Graphs.
- Author
-
Cabrera Martínez, Abel, Montejano, Luis P., and Rodríguez-Velázquez, Juan A.
- Subjects
- *
DOMINATING set , *GEODESICS - Abstract
A total dominating set D of a graph G is said to be a secure total dominating set if for every vertex u ∈ V (G) \ D , there exists a vertex v ∈ D , which is adjacent to u, such that (D \ { v }) ∪ { u } is a total dominating set as well. The secure total domination number of G is the minimum cardinality among all secure total dominating sets of G. In this article, we obtain new relationships between the secure total domination number and other graph parameters: namely the independence number, the matching number and other domination parameters. Some of our results are tight bounds that improve some well-known results. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
11. The Cyclic Triangle-Free Process.
- Author
-
Jiang, Yu, Liang, Meilian, Teng, Yanmei, and Xu, Xiaodong
- Subjects
- *
RAMSEY numbers , *INDEPENDENT sets , *ORDERED sets , *INTEGERS - Abstract
For positive integers s and t, the Ramsey number R (s , t) is the smallest positive integer n such that every graph of order n contains either a clique of order s or an independent set of order t. The triangle-free process begins with an empty graph of order n, and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed. It has been an important tool in studying the asymptotic lower bound for R (3 , t) . Cyclic graphs are vertex-transitive. The symmetry of cyclic graphs makes it easier to compute their independent numbers than related general graphs. In this paper, the cyclic triangle-free process is studied. The sizes of the parameter sets and the independence numbers of the graphs obtained by the cyclic triangle-free process are studied. Lower bounds on R (3 , t) for small t's are computed, and R (3 , 35) ≥ 237 , R (3 , 36) ≥ 244 , R (3 , 37) ≥ 255 , R (3 , 38) ≥ 267 , etc. are obtained based on the graphs obtained by the cyclic triangle-free process. Finally, some problems on the cyclic triangle-free process and R (3 , t) are proposed. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
12. Role of Graphic Integer Sequence in the Determination of Graph Integrity.
- Author
-
Sensarma, Debajit and Sen Sarma, Samar
- Subjects
- *
GRAPH connectivity , *INTEGERS , *MATHEMATICAL sequences , *INTEGRITY , *RANDOM graphs , *TELECOMMUNICATION systems - Abstract
Networks have an important role in our daily lives. The effectiveness of the network decreases with the breaking down of some vertices or links. Therefore, a less vulnerable communication network is required for greater stability. Vulnerability is the measure of resistance of the network after failure of communication links. In this article, a graph has been taken for modeling a network and integrity as a measure of vulnerability. The approach is to estimate the integrity or upper bound of integrity of at least one connected graph or network constructed from the given graphic integer sequence. Experiments have been done with random graphs, complex networks and also a comparison between two parameters, namely the vertex connectivity and graph integrity as a measure of the network vulnerability have been carried out by removing vertices randomly from various complex networks. A comparison with the existing method shows that the algorithm proposed in this article provides a much better integrity measurement. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
13. Matching Number, Independence Number, and Covering Vertex Number of Γ(Zn).
- Author
-
AbuHijleh, Eman, Abudayah, Mohammad, Alomari, Omar, and Al-Ezeh, Hasan
- Subjects
- *
MATHEMATICAL symmetry , *NUMBER theory , *GRAPH theory , *ISOMORPHISM (Mathematics) , *SET theory , *MATCHING theory - Abstract
Graph invariants are the properties of graphs that do not change under graph isomorphisms, the independent set decision problem, vertex covering problem, and matching number problem are known to be NP-Hard, and hence it is not believed that there are efficient algorithms for solving them. In this paper, the graph invariants matching number, vertex covering number, and independence number for the zero-divisor graph over the rings Z p k and Z p k q r are determined in terms of the sets S p i and S p i q j respectively. Accordingly, a formula in terms of p , q , k , and r, with n = p k , n = p k q r is provided. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.