63 results on '"Independence number"'
Search Results
2. On the maximum atom-bond sum-connectivity index of graphs
- Author
-
Alraqad Tariq, Saber Hicham, Ali Akbar, and Albalahi Abeer M.
- Subjects
topological index ,atom-bond sum-connectivity ,independence number ,pendent vertex ,chromatic number ,05c07 ,05c09 ,05c35 ,Mathematics ,QA1-939 - Abstract
The atom-bond sum-connectivity (ABS) index of a graph GG with edges e1,…,em{e}_{1},\ldots ,{e}_{m} is the sum of the numbers 1−2(dei+2)−1\sqrt{1-2{\left({d}_{{e}_{i}}+2)}^{-1}} over 1≤i≤m1\le i\le m, where dei{d}_{{e}_{i}} is the number of edges adjacent to ei{e}_{i}. In this article, we study the maximum values of the ABS index over graphs with given parameters. More specifically, we determine the maximum ABS index of connected graphs of a given order with a fixed (i) minimum degree, (ii) maximum degree, (iii) chromatic number, (iv) independence number, or (v) number of pendent vertices. We also characterize the graphs attaining the maximum ABS values in all of these classes.
- Published
- 2024
- Full Text
- View/download PDF
3. Integral sum graphs Gn and G-r,n are perfect graphs
- Author
-
Julia K. Abraham, Sajidha P., Lowell W. Beineke, Vilfred V., and L. Mary Florida
- Subjects
Integral sum graph ,covering number ,independence number ,chromatic number ,clique number ,perfect graphs ,Mathematics ,QA1-939 - Abstract
AbstractA graph G is an integral sum graph (sum graph) if its vertices can be labeled with distinct integers (positive integers) so that e = uv is an edge of G if and only if the sum of the labels on vertices u and v is also a label in G. A graph G is perfect if the chromatic number of each of its induced subgraphs is equal to the clique number of the same. A simple graph G is of class 1 if its edge chromatic number and maximum degree are same. In this paper, we prove that integral sum graphs Gn, [Formula: see text] and [Formula: see text] over the label sets [Formula: see text] and [Formula: see text], respectively, are perfect graphs as well as of class 1 for [Formula: see text]. We also obtain a few structural properties of these graphs.
- Published
- 2024
- Full Text
- View/download PDF
4. Prime labeling of graphs constructed from wheel graph
- Author
-
Baha' Abughazaleh and Omar A. Abughneim
- Subjects
Independence number ,Wheels ,Prime labeling ,Prime graphs ,Science (General) ,Q1-390 ,Social sciences (General) ,H1-99 - Abstract
A prime labeling of a simple undirected graph G is to assign unique integer labels from the set {1,2,...,|V(G)|} to each vertex such that any two adjacent vertices in the graph have labels that are relatively prime. Studying prime labeling in graphs can help us understand the structure and properties of graphs and prime labeling has potential applications in cryptography and network security. In this paper we investigate when some graphs that are constructed from wheels are prime graphs.
- Published
- 2024
- Full Text
- View/download PDF
5. Semi Square Stable Graphs and Efficient Dominating Sets
- Author
-
Baha̓ Abughazaleh and Omar Abughneim
- Subjects
independence number ,independent dominating number ,efficient dominating sets ,semi square stable graphs ,graph operations ,Mathematics ,QA1-939 - Abstract
A graph $G$ is called semi square stable if $\alpha (G^{2})=i(G)$ where $%\alpha (G^{2})$ is the independence number of $G^{2}$ and $i(G)$ is the independent dominating number of $G$. A subset $S$ of the vertex set of a graph $G$ is an efficient dominating set if $S$ is an independent set and every vertex of $G$ is either in $S$ or adjacent to exactly one vertex of $%S. $In this paper, we show that every square stable graph has an efficient dominating set and if a graph has an efficient dominating set, then it is semi square stable. We characterize when the join and the corona product of two disjoint graphs are semi square sable graphs and when they have efficient dominating sets.
- Published
- 2023
- Full Text
- View/download PDF
6. The differential on operator S(Γ)
- Author
-
Jair Castro, Ludwin A. Basilio, Gerardo Reyna, and Omar Rosario
- Subjects
subdivision graph ,differential of graphs ,independence number ,matching number ,Biotechnology ,TP248.13-248.65 ,Mathematics ,QA1-939 - Abstract
Consider a simple graph $ \Gamma = (V(\Gamma), E(\Gamma)) $ with $ n $ vertices and $ m $ edges. Let $ P $ be a subset of $ V(\Gamma) $ and $ B(P) $ the set of neighbors of $ P $ in $ V(\Gamma)\backslash P $. In the study of graphs, the concept of differential refers to a measure of how much the number of edges leaving a set of vertices exceeds the size of that set. Specifically, given a subset $ P $ of vertices, the differential of $ P $, denoted by $ \partial(P) $, is defined as $ |B(P)|-|P| $. The differential of $ \Gamma $, denoted by $ \partial(\Gamma) $, is then defined as the maximum differential over all possible subsets of $ V(\Gamma) $. Additionally, the subdivision operator $ {{\mathcal{S}}({\Gamma})} $ is defined as the graph obtained from $ \Gamma $ by inserting a new vertex on each edge of $ \Gamma $. In this paper, we present results for the differential of graphs on the subdivision operator $ {{\mathcal{S}}({\Gamma})} $ where some of these show exact values of $ \partial({{\mathcal{S}}({\Gamma})}) $ if $ \Gamma $ belongs to a classical family of graphs. We obtain bounds for $ \partial({{\mathcal{S}}({\Gamma})}) $ involving invariants of a graph such as order $ n $, size $ m $ and maximum degree $ \Delta $, and we study the realizability of the graph $ \Gamma $ for any value of $ \partial({{\mathcal{S}}({\Gamma})}) $ in the interval $ \left[n-2, \frac{n(n-1)}{2}-n+2\right] $. Moreover, we give a characterization for $ \partial({{\mathcal{S}}({\Gamma})}) $ using the notion of edge star packing.
- Published
- 2023
- Full Text
- View/download PDF
7. $ Z_{3} $-connectivity of graphs with independence number at most 3
- Author
-
Chunyan Qin, Xiaoxia Zhang, and Liangchen Li
- Subjects
nowhere-zero flows ,z3-connectivity ,independence number ,Mathematics ,QA1-939 - Abstract
It was conjectured by Jaeger et al. that all 5-edge-connected graphs are $ Z_3 $-connected. In this paper, we confirm this conjecture for all 5-edge-connected graphs with independence number at most 3.
- Published
- 2023
- Full Text
- View/download PDF
8. Bounds on the Clique and the Independence Number for Certain Classes of Graphs
- Author
-
Valentin E. Brimkov and Reneta P. Barneva
- Subjects
degree-equivalent graphs ,clique ,independent set ,vertex cover ,clique number ,independence number ,Mathematics ,QA1-939 - Abstract
In this paper, we study the class of graphs Gm,n that have the same degree sequence as two disjoint cliques Km and Kn, as well as the class G¯m,n of the complements of such graphs. The problems of finding a maximum clique and a maximum independent set are NP-hard on Gm,n. Therefore, looking for upper and lower bounds for the clique and independence numbers of such graphs is a challenging task. In this article, we obtain such bounds, as well as other related results. In particular, we consider the class of regular graphs, which are degree-equivalent to arbitrarily many identical cliques, as well as such graphs of bounded degree.
- Published
- 2024
- Full Text
- View/download PDF
9. Some Properties of the Nil-Graphs of Ideals of Commutative Rings
- Author
-
Reza Nikandish
- Subjects
nil-graph ,complete graph ,bipartite graph ,genus ,independence number ,Mathematics ,QA1-939 - Abstract
Let R be a commutative ring with identity and Nil(R) be the set of nilpotent elements of R. The nil-graph of ideals of R is defined as the graph AG_N(R) whose vertex set is {I:(0)and there exists a non-trivial ideal such that and two distinct vertices and are adjacent if and only if . Here, we study conditions under which is complete or bipartite. Also, the independence number of is determined, where is a reduced ring. Finally, we classify Artinian rings whose nil-graphs of ideals have genus at most one.
- Published
- 2022
10. Discontinuity and diversity of Persian scientific research journals in the field of educational sciences by using coloring and mathematical algebraic parameters
- Author
-
Ali Abdi and Mostafa Amini
- Subjects
cluster number ,color number ,independence number ,matching number ,scientific etwork of educational sciences ,Mathematics ,QA1-939 ,History of education ,LA5-2396 - Abstract
The aim of the current research is to study and compare graphs authorship by Iranian researchers in Persian scientific research journals in the field of educational sciences by using algebraic parameters of mathematics. In this research, the data related to the scientific research documents of 336 Iranian researchers from 6 Persian scientific research journals in the field of educational sciences from 2017 to 2021 were extracted by using the issues printed in these journals and the graphs related to the authors of these journals have been drawn by mathematical methods and software, and then compared and analyzed by using algebraic parameters such as the average degrees of vertices, independence, color and matching numbers. In the main results, it was checked that the average grade of the Journal of the Educational Measurement and Evaluation Studies is 4.4 and higher than other journals. Also, the largest research group (cluster number) is 6 people, and the most research diversity (independence number) is 29 and it is related to of the Journal of the teaching research. Among the discussed journals in the field of educational sciences, according to the average grades, the amount of research cooperation of the Journal of Educational Measurement and Evaluation Studies is at a higher level than the other five journals.
- Published
- 2022
- Full Text
- View/download PDF
11. New Results Relating Independence and Matchings
- Author
-
Caro Yair, Davila Randy, and Pepper Ryan
- Subjects
independent sets ,independence number ,matchings ,matching number ,05c69 ,Mathematics ,QA1-939 - Abstract
In this paper we study relationships between the matching number, written µ(G), and the independence number, written α(G). Our first main result is to show
- Published
- 2022
- Full Text
- View/download PDF
12. On the strength and independence number of graphs
- Author
-
Rikio Ichishima, Francesc A. Muntaner-Batle, and Yukio Takahashi
- Subjects
strength ,independence number ,k-stable ,graph labeling ,combinatorial optimization ,Mathematics ,QA1-939 - Published
- 2022
- Full Text
- View/download PDF
13. Further Results on Packing Related Parameters in Graphs
- Author
-
Mojdeh Doost Ali, Samadi Babak, and Yero Ismael G.
- Subjects
packing number ,open packing number ,independence number ,nordhaus-gaddum inequality ,total domination number ,05c69 ,Mathematics ,QA1-939 - Abstract
Given a graph G = (V, E), a set B ⊆ V (G) is a packing in G if the closed neighborhoods of every pair of distinct vertices in B are pairwise disjoint. The packing number ρ(G) of G is the maximum cardinality of a packing in G. Similarly, open packing sets and open packing number are defined for a graph G by using open neighborhoods instead of closed ones. We give several results concerning the (open) packing number of graphs in this paper. For instance, several bounds on these packing parameters along with some Nordhaus-Gaddum inequalities are given. We characterize all graphs with equal packing and independence numbers and give the characterization of all graphs for which the packing number is equal to the independence number minus one. In addition, due to the close connection between the open packing and total domination numbers, we prove a new upper bound on the total domination number γt(T) for a tree T of order n ≥ 2 improving the upper bound γt(T) ≤ (n + s)/2 given by Chellali and Haynes in 2004, in which s is the number of support vertices of T.
- Published
- 2022
- Full Text
- View/download PDF
14. On the Independence Number of Cayley Digraphs of Clifford Semigroups
- Author
-
Krittawit Limkul and Sayan Panma
- Subjects
Cayley digraph ,Clifford semigroup ,independent set ,independence number ,Mathematics ,QA1-939 - Abstract
Let S be a Clifford semigroup and A a subset of S. We write Cay(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 Cay(S,A) and apply these results to determine the (weak, path, weak path) independence number of Cay(S,A).
- Published
- 2023
- Full Text
- View/download PDF
15. On graphs with minimal distance signless Laplacian energy
- Author
-
Pirzada S., Rather Bilal A., Shaban Rezwan Ul, and Merajuddin
- Subjects
distance signless laplacian matrix ,independence number ,vertex connectivity ,extremal graphs ,05c12 ,05c50 ,15a18 ,Mathematics ,QA1-939 - Abstract
For a simple connected graph G of order n having distance signless Laplacian eigenvalues ρ1Q≥ρ2Q≥⋯≥ρnQ\rho _1^Q \ge \rho _2^Q \ge \cdots \ge \rho _n^Q, the distance signless Laplacian energy DSLE(G) is defined as DSLE(G)=∑i=1n|ρiQ-2W(G)n|DSLE\left( G \right) = \sum\nolimits_{i = 1}^n {\left| {\rho _i^Q - {{2W\left( G \right)} \over n}} \right|} where W(G) is the Weiner index of G. We show that the complete split graph has the minimum distance signless Laplacian energy among all connected graphs with given independence number. Further, we prove that the graph Kk ∨ ( Kt∪ Kn−k−t),1≤t≤⌊n-k2⌋1 \le t \le \left\lfloor {{{n - k} \over 2}} \right\rfloor has the minimum distance signless Laplacian energy among all connected graphs with vertex connectivity k.
- Published
- 2021
- Full Text
- View/download PDF
16. A note on subspace sum graph of vector spaces
- Author
-
Ramanathan Venkatasalam and Selvaraj Chelliah
- Subjects
subspace sum graph ,vector space ,independence number ,graph embedding ,Mathematics ,QA1-939 - Abstract
For a finite dimensional vector space over a field the subspace sum graph of denoted by is defined to be a simple undirected graph with vertex set as the set of all non-trivial proper subspace of and, for any two distinct vertices V1 and V2 are adjacent if and only if In this paper, we establish some inter-relationship between as a graph and as a vector space by the study of genus of subspace sum graph of vector spaces. In particular, we characterize the collection of all the vector spaces for which the subspace sum graph of is either planar, toroidal or bi-toroidal. Furthermore, we determine the independence number of for a vector space of dimension at most 5.
- Published
- 2021
- Full Text
- View/download PDF
17. Parameters of the coprime graph of a group
- Author
-
Jessie Hamm and Alan Way
- Subjects
coprime graph ,finite groups ,independence number ,perfect graph ,Mathematics ,QA1-939 - Abstract
There are many different graphs one can associate to a group. Some examples are the well-known Cayley graph, the zero divisor graph (of a ring), the power graph, and the recently introduced coprime graph of a group. The coprime graph of a group $G$, denoted $\Gamma_G$, is the graph whose vertices are the group elements with $g$ adjacent to $h$ if and only if $(o(g),o(h))=1$. In this paper we calculate the independence number of the coprime graph of the dihedral groups. Additionally, we characterize the groups whose coprime graph is perfect.
- Published
- 2021
- Full Text
- View/download PDF
18. Independence Number and Packing Coloring of Generalized Mycielski Graphs
- Author
-
Bidine Ez Zobair, Gadi Taoufiq, and Kchikech Mustapha
- Subjects
independence number ,packing chromatic number ,mycielskians ,generalized mycielskians ,05c15 ,05c70 ,05c12 ,Mathematics ,QA1-939 - Abstract
For a positive integer k ⩾ 1, a graph G with vertex set V is said to be k-packing colorable if there exists a mapping f : V ↦ {1, 2, . . ., k} such that any two distinct vertices x and y with the same color f(x) = f(y) are at distance at least f(x) + 1. The packing chromatic number of a graph G, denoted by χρ(G), is the smallest integer k such that G is k-packing colorable.
- Published
- 2021
- Full Text
- View/download PDF
19. Spanning k-Ended Tree in 2-Connected Graph
- Author
-
Wanpeng Lei and Jun Yin
- Subjects
connectivity ,independence number ,k-ended tree ,maximum independent set ,Mathematics ,QA1-939 - 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)K1∪Kn−2κ−k+1).
- Published
- 2023
- Full Text
- View/download PDF
20. Recent developments on the power graph of finite groups – a survey
- Author
-
Ajay Kumar, Lavanya Selvaganesh, Peter J. Cameron, and T. Tamizh Chelvam
- Subjects
group ,power graph ,connectivity ,spectrum ,automorphism ,isomorphism ,independence number ,Mathematics ,QA1-939 - Abstract
Algebraic graph theory is the study of the interplay between algebraic structures (both abstract as well as linear structures) and graph theory. Many concepts of abstract algebra have facilitated through the construction of graphs which are used as tools in computer science. Conversely, graph theory has also helped to characterize certain algebraic properties of abstract algebraic structures. In this survey, we highlight the rich interplay between the two topics viz groups and power graphs from groups. In the last decade, extensive contribution has been made towards the investigation of power graphs. Our main motive is to provide a complete survey on the connectedness of power graphs and proper power graphs, the Laplacian and adjacency spectrum of power graph, isomorphism, and automorphism of power graphs, characterization of power graphs in terms of groups. Apart from the survey of results, this paper also contains some new material such as the contents of Section 2 (which describes the interesting case of the power graph of the Mathieu group M11) and Section 6.1 (where conditions are discussed for the reduced power graph to be not connected). We conclude this paper by presenting a set of open problems and conjectures on power graphs.
- Published
- 2021
- Full Text
- View/download PDF
21. Connected Domination Number and a New Invariant in Graphs with Independence Number Three
- Author
-
Vladimir Bercov
- Subjects
dominating set ,number of hadwiger ,clique number ,independence number ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
Adding a connected dominating set of vertices to a graph $G$ increases its number of Hadwiger $h(G)$. Based on this obvious property in [2] we introduced a new invariant $\eta(G)$ for which $\eta(G)\leq h(G)$. We continue to study its property. For a graph $G$ with independence number three without induced chordless cycles $C_7$ and with $n(G)$ vertices, $\eta(G)\geq n(G)/4$.
- Published
- 2021
22. Maximum H-index of bipartite network with some given parameters
- Author
-
Shahid Zaman, Fouad A. Abolaban, Ali Ahmad, and Muhammad Ahsan Asim
- Subjects
h-index ,bipartite network ,matching number ,independence number ,cover of a network ,diameter ,Mathematics ,QA1-939 - Abstract
A network is an abstract structure that consists of nodes that are connected by links. A bipartite network is a type of networks where the set of nodes can be divided into two disjoint sets in a way that each link connects a node from one partition with a node from the other partition. In this paper, we first determine the maximum H-index of networks in the class of all n-node connected bipartite network with matching number t. We obtain that the maximum H-index of a bipartite network with a given matching number is Kt,n−t. Secondly, we characterize the network with the maximum H-index in the class of all the n-vertex connected bipartite network of given diameter. Based on our obtain results, we establish the unique bipartite network with maximum H-index among bipartite networks with a given independence number and cover of a network.
- Published
- 2021
- Full Text
- View/download PDF
23. Independent Transversal Total Domination Versus Total Domination in Trees
- Author
-
Martínez Abel Cabrera, Peterin Iztok, and Yero Ismael G.
- Subjects
independent transversal total domination number ,total domination number ,independence number ,trees ,05c69 ,05c05 ,Mathematics ,QA1-939 - Abstract
A subset of vertices in a graph G is a total dominating set if every vertex in G is adjacent to at least one vertex in this subset. The total domination number of G is the minimum cardinality of any total dominating set in G and is denoted by γt(G). A total dominating set of G having nonempty intersection with all the independent sets of maximum cardinality in G is an independent transversal total dominating set. The minimum cardinality of any independent transversal total dominating set is denoted by γtt(G). Based on the fact that for any tree T, γt(T) ≤ γtt(T) ≤ γt(T) + 1, in this work we give several relationships between γtt(T) and γt(T) for trees T which are leading to classify the trees which are satisfying the equality in these bounds.
- Published
- 2021
- Full Text
- View/download PDF
24. On Trees with Given Independence Numbers with Maximum Gourava Indices
- Author
-
Ying Wang, Adnan Aslam, Nazeran Idrees, Salma Kanwal, Nabeela Iram, and Asima Razzaque
- Subjects
tree ,spur tree ,independence number ,Gourava indices ,Mathematics ,QA1-939 - 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 GO1(N)=∑u′v′∈E(N)(d(u′)+d(v′)+d(u′)d(v′)) and GO2(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.
- Published
- 2023
- Full Text
- View/download PDF
25. The independence number of circulant triangle-free graphs
- Author
-
S. Masih Ayat, S. Majid Ayat, and Meysam Ghahramani
- Subjects
triangular-free graphs ,circulant graphs ,independence number ,independence ratio ,ramsey graphs ,Mathematics ,QA1-939 - Abstract
The independence number of circulant triangle-free graphs for 2-regular, 3-regular graphs are investigated. It is shown that the independence ratio of circulant triangle-free graphs for 3-regular graphs is at least 3/8. Some bounds for the number of vertices of r-regular circulant triangle-free graphs with independence number equal to r for odd degrees are determined. These bounds are close to Sidorenko’s bounds for even degrees.
- Published
- 2020
- Full Text
- View/download PDF
26. On the 2-token graph of a graph
- Author
-
J. Deepalakshmi, G. Marimuthu, A. Somasundaram, and S. Arumugam
- Subjects
-token graph ,line graph ,chordal graph ,independence number ,Mathematics ,QA1-939 - Abstract
Let be a graph and let be a positive integer. Let = and . The -token graph is the graph with vertex set and two vertices and are adjacent if and , where denotes the symmetric difference. In this paper we present several basic results on 2-token graphs.
- Published
- 2020
- Full Text
- View/download PDF
27. On the Independence Number of Traceable 2-Connected Claw-Free Graphs
- Author
-
Wang Shipeng and Xiong Liming
- Subjects
traceability ,independence number ,matching number ,trail ,closure ,05c38 ,05c69 ,05c70 ,Mathematics ,QA1-939 - Abstract
A well-known theorem by Chvátal-Erdőos [A note on Hamilton circuits, Discrete Math. 2 (1972) 111–135] states that if the independence number of a graph G is at most its connectivity plus one, then G is traceable. In this article, we show that every 2-connected claw-free graph with independence number α(G) ≤ 6 is traceable or belongs to two exceptional families of well-defined graphs. As a corollary, we also show that every 2-connected claw-free graph with independence number α(G) ≤ 5 is traceable.
- Published
- 2019
- Full Text
- View/download PDF
28. On 3-Colorings of Direct Products of Graphs
- Author
-
Špacapan Simon
- Subjects
independence number ,direct product ,hedetniemi’s conjecture ,05c15 ,05c69 ,05c67 ,Mathematics ,QA1-939 - Abstract
The k-independence number of a graph G, denoted as αk(G), is the order of a largest induced k-colorable subgraph of G. In [S. Špacapan, The k-independence number of direct products of graphs, European J. Combin. 32 (2011) 1377–1383] the author conjectured that the direct product G × H of graphs G and H obeys the following bound
- Published
- 2019
- Full Text
- View/download PDF
29. New Formulae for the Decycling Number of Graphs
- Author
-
Yang Chao and Ren Han
- Subjects
decycling number ,independence number ,cycle rank ,margin number ,05c07 ,05c38 ,Mathematics ,QA1-939 - Abstract
A set S of vertices of a graph G is called a decycling set if G−S is acyclic. The minimum order of a decycling set is called the decycling number of G, and denoted by ∇(G). Our results include: (a) For any graph G,, where T is taken over all the spanning trees of G and α(G − E(T)) is the independence number of the co-tree G − E(T). This formula implies that computing the decycling number of a graph G is equivalent to finding a spanning tree in G such that its co-tree has the largest independence number. Applying the formula, the lower bounds for the decycling number of some (dense) graphs may be obtained. (b) For any decycling set S of a k-regular graph G, where β(G) = |E(G)|−|V (G)|+1 and m(S) = c+|E(S)|−1, c and |E(S)| are, respectively, the number of components of G − S and the number of edges in G[S]. Hence S is a ∇-set if and only if m(S) is minimum, where∇-set denotes a decycling set containing exactly ∇(G) vertices of G. This provides a new way to locate ∇(G) for k-regular graphs G. (c) 4-regular graphs G with the decycling number are determined.
- Published
- 2019
- Full Text
- View/download PDF
30. Independence Number, Connectivity and All Fractional (a, b, k)-Critical Graphs
- Author
-
Yuan Yuan and Hao Rong-Xia
- Subjects
independence number ,connectivity ,fractional [a ,b]-factor ,frac- tional (a ,k)-critical graph ,all fractional (a ,05c70 ,05c72 ,Mathematics ,QA1-939 - Abstract
Let G be a graph and a, b and k be nonnegative integers with 1 ≤ a ≤ b. A graph G is defined as all fractional (a, b, k)-critical if after deleting any k vertices of G, the remaining graph has all fractional [a, b]-factors. In this paper, we prove that if , then G is all fractional (a, b, k) -critical. If k = 0, we improve the result given in [Filomat 29 (2015) 757-761]. Moreover, we show that this result is best possible in some sense.
- Published
- 2019
- Full Text
- View/download PDF
31. Two Degree Distance Based Topological Indices of Chemical Trees
- Author
-
Shehnaz Akhter
- Subjects
Eccentric connectivity index ,eccentric adjacency index ,bipartition ,matching number ,independence number ,domination number ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 - Abstract
Let G = (VG, EG) be a simple and connected graph. The eccentric connectivity index of G is represented as ξc(G) = Σx∈VG degG(x)ecG(x), where degG(x) and ecG(x) represent the degree and the eccentricity of x, respectively. The eccentric adjacency index of G is represented as ξad(G) = Σx∈VG (SG(x)/ecG(x)), where SQ(x) is the sum of degrees of neighbors of x. In this paper, we determine the trees with the smallest eccentric connectivity index when bipartition size, independence number, and domination number are given. Furthermore, we discuss the trees with the largest eccentric adjacency index when bipartition size, matching number, and independence number are given.
- Published
- 2019
- Full Text
- View/download PDF
32. Some results on the independence number of connected domination critical graphs
- Author
-
P. Kaemawichanurat and T. Jiarasuksakun
- Subjects
domination ,connected domination ,-critical graphs ,clique number ,independence number ,Mathematics ,QA1-939 - Abstract
A --critical graph is a graph with connected domination number and for any pair of non-adjacent vertices and of . Let and be respectively the clique number and the independence number of a graph. In this paper, we prove that every --critical graph satisfies for . We also characterize all --critical graphs achieving the upper bound. For , we show that there are infinitely many --critical graphs satisfying . Thus, we conclude this paper with an open problem that every --critical graph for satisfies .
- Published
- 2018
- Full Text
- View/download PDF
33. Bounds for the Independence Number in $k$-Step Hamiltonian Graphs
- Author
-
Noor A'lawiah Abd Aziz, Nader Jafari Rad, Hailiza Kamarulhaili, and Roslan Hasni
- Subjects
Independence number ,Hamiltonian graph ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
For a given integer $k$, a graph $G$ of order $n$ is called $k$-step Hamiltonian if there is a labeling $v_1,v_2,...,v_n$ of vertices of $G$ such that $d(v_1,v_n)=d(v_i,v_{i+1})=k$ for $i=1,2,...,n-1$. The independence number of a graph is the maximum cardinality of a subset of pair-wise non-adjacent vertices. In this paper we study the independence number in $k$-step Hamiltonian graphs. We present sharp upper bounds as well as sharp lower bounds, and then present a construction that produces infinite families of $k$-step Hamiltonian graphs with arbitrarily large independence number.
- Published
- 2018
34. On Selkow’s Bound on the Independence Number of Graphs
- Author
-
Harant Jochen and Mohr Samuel
- Subjects
graph ,independence number ,05c69 ,Mathematics ,QA1-939 - Abstract
For a graph G with vertex set V (G) and independence number α(G), Selkow [A Probabilistic lower bound on the independence number of graphs, Discrete Math. 132 (1994) 363–365] established the famous lower bound ∑v∈V(G)1d(v)+1(1+max{d(v)d(v)+1-∑u∈N(v)1d(u)+1,0})$\sum {_{v \in V(G)}{1 \over {d(v) + 1}}} \left( {1 + \max \left\{ {{{d(v)} \over {d(v) + 1}} - \sum {_{u \in N(v)}{1 \over {d(u) + 1}},0} } \right\}} \right)$ on α (G), where N(v) and d(v) = |N(v)| denote the neighborhood and the degree of a vertex v ∈ V (G), respectively. However, Selkow’s original proof of this result is incorrect. We give a new probabilistic proof of Selkow’s bound here.
- Published
- 2019
- Full Text
- View/download PDF
35. General Properties on Differential Sets of a Graph
- Author
-
Ludwin A. Basilio, Sergio Bermudo, Juan C. Hernández-Gómez, and José M. Sigarreta
- Subjects
differential ,domination number ,independence number ,Mathematics ,QA1-939 - 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|suchthatS⊆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.
- Published
- 2021
- Full Text
- View/download PDF
36. On θ-commutators and the corresponding non-commuting graphs
- Author
-
Shalchi S., Erfanian A., and Farrokhi DG M.
- Subjects
commutator ,automorphism ,independence number ,chromatic number ,multipartite graph ,05c25 ,05c15 ,05c69 ,20d45 ,20f12 ,Mathematics ,QA1-939 - Abstract
The θ-commutators of elements of a group with respect to an automorphism are introduced and their properties are investigated. Also, corresponding to θ-commutators, we define the θ-non-commuting graphs of groups and study their correlations with other notions. Furthermore, we study independent sets in θ-non-commuting graphs, which enable us to evaluate the chromatic number of such graphs.
- Published
- 2017
- Full Text
- View/download PDF
37. Common Independence in Graphs
- Author
-
Magda Dettlaff, Magdalena Lemańska, and Jerzy Topp
- Subjects
independence number ,domination number ,independence domination number ,common independence number ,Mathematics ,QA1-939 - 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 VG 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).
- Published
- 2021
- Full Text
- View/download PDF
38. New bound on MIS and MIN-CDS for a unit ball graph
- Author
-
D.A. Mojdeh, M. Ghanbari, and M. Ramezani
- Subjects
Connected dominating set ,Independence number ,Unit ball graph ,Information technology ,T58.5-58.64 - Abstract
The size of the maximum independent set (MIS) in a graph G is called the independence number. The size of the minimum connected dominating set (MIN-CDS) in G is called the connected domination number. The aim of this paper is to determine two better upper bounds of the independence number; dependent on the connected domination number for a unit ball graph. Further, we improve the upper bound to obtain the best bound with respect to the upper bounds obtained thus far.
- Published
- 2017
- Full Text
- View/download PDF
39. On Generalized Sierpiński Graphs
- Author
-
Rodríguez-Velázquez Juan Alberto, Rodríguez-Bazan Erick David, and Estrada-Moreno Alejandro
- Subjects
sierpiński graphs ,vertex cover number ,independence number ,chromatic number ,domination number ,05c76 ,05c69 ,05c15 ,Mathematics ,QA1-939 - Abstract
In this paper we obtain closed formulae for several parameters of generalized Sierpiński graphs S(G, t) in terms of parameters of the base graph G. In particular, we focus on the chromatic, vertex cover, clique and domination numbers.
- Published
- 2017
- Full Text
- View/download PDF
40. Some results on the comaximal ideal graph of a commutative ring
- Author
-
Hamid Reza Dorbidi and Raoufeh Manaviyat
- Subjects
Comaximal ideal graph ,Genus of graph ,Domination Number ,Independence number ,Mathematics ,QA1-939 - Abstract
Let $R$ be a commutative ring with unity. The comaximal ideal graph of $R$, denoted by $mathcal{C}(R)$, is a graph whose vertices are the proper ideals of $R$ which are not contained in the Jacobson radical of $R$, and two vertices $I_1$ and $I_2$ are adjacent if and only if $I_1 +I_2 = R$. In this paper, we classify all comaximal ideal graphs with finite independence number and present a formula to calculate this number. Also, the domination number of $mathcal{C}(R)$ for a ring $R$ is determined. In the last section, we introduce all planar and toroidal comaximal ideal graphs. Moreover, the commutative rings with isomorphic comaximal ideal graphs are characterized. In particular we show that every finite comaximal ideal graph is isomorphic to some $mathcal{C}(mathbb{Z}_n)$.
- Published
- 2016
- Full Text
- View/download PDF
41. Some results on the comaximal ideal graph of a commutative ring
- Author
-
Hamid Reza Dorbidi and Raoufeh Manaviyat
- Subjects
Comaximal ideal graph ,Genus of graph ,Domination number ,Independence number ,Mathematics ,QA1-939 - Abstract
Let R R be a commutative ring with unity. The comaximal ideal graph of R R, denoted by C(R) C(R), is a graph whose vertices are the proper ideals of R R which are not contained in the Jacobson radical of R R, and two vertices I 1 I1 and I 2 I2 are adjacent if and only if I 1 +I 2 =R I1+I2=R. In this paper, we classify all comaximal ideal graphs with finite independence number and present a formula to calculate this number. Also, the domination number of C(R) C(R) for a ring R R is determined. In the last section, we introduce all planar and toroidal comaximal ideal graphs. Moreover, the commutative rings with isomorphic comaximal ideal graphs are characterized. In particular we show that every finite comaximal ideal graph is isomorphic to some C(Z n ) C(Zn).
- Published
- 2016
42. Graphs with Minimal Strength
- Author
-
Zhen-Bin Gao, Gee-Choon Lau, and Wai-Chee Shiu
- Subjects
strength ,minimum degree ,δ-sequence ,independence number ,2-regular ,Mathematics ,QA1-939 - Abstract
For any graph G of order p, a bijection f:V(G)→{1,2,…,p} is called a numbering of G. The strength strf(G) of a numbering f of G is defined by strf(G)=max{f(u)+f(v)|uv∈E(G)}, and the strength str(G) of a graph G is str(G)=min{strf(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.
- Published
- 2021
- Full Text
- View/download PDF
43. On Sombor Index
- Author
-
Kinkar Chandra Das, Ahmet Sinan Çevik, Ismail Naci Cangul, and Yilun Shang
- Subjects
graph ,sombor index ,maximum degree ,minimum degree ,independence number ,Mathematics ,QA1-939 - Abstract
The concept of Sombor index (SO) was recently introduced by Gutman in the chemical graph theory. It is a vertex-degree-based topological index and is denoted by Sombor index SO: SO=SO(G)=∑vivj∈E(G)dG(vi)2+dG(vj)2, where dG(vi) is the degree of vertex vi 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.
- Published
- 2021
- Full Text
- View/download PDF
44. Looseness and Independence Number of Triangulations on Closed Surfaces
- Author
-
Nakamoto Atsuhiro, Negami Seiya, Ohba Kyoji, and Suzuki Yusuke
- Subjects
triangulations ,closed surfaces ,looseness ,k-loosely tight ,independence number ,Mathematics ,QA1-939 - Abstract
The looseness of a triangulation G on a closed surface F2, denoted by ξ (G), is defined as the minimum number k such that for any surjection c : V (G) → {1, 2, . . . , k + 3}, there is a face uvw of G with c(u), c(v) and c(w) all distinct. We shall bound ξ (G) for triangulations G on closed surfaces by the independence number of G denoted by α(G). In particular, for a triangulation G on the sphere, we have
- Published
- 2016
- Full Text
- View/download PDF
45. The Quest for A Characterization of Hom-Properties of Finite Character
- Author
-
Broere Izak, Matsoha Moroli D.V., and Heidema Johannes
- Subjects
(countable) graph ,homomorphism (of graphs) ,property of graphs ,hom-property ,(finitely-)induced-hereditary property ,finitely determined property ,(weakly) finite character ,axiomatizable property ,compactness theorems ,core ,connectedness ,chromatic number ,clique number ,independence number ,dominating set ,Mathematics ,QA1-939 - Abstract
A graph property is a set of (countable) graphs. A homomorphism from a graph G to a graph H is an edge-preserving map from the vertex set of G into the vertex set of H; if such a map exists, we write G → H. Given any graph H, the hom-property →H is the set of H-colourable graphs, i.e., the set of all graphs G satisfying G → H. A graph property P is of finite character if, whenever we have that F ∈ P for every finite induced subgraph F of a graph G, then we have that G ∈ P too. We explore some of the relationships of the property attribute of being of finite character to other property attributes such as being finitely-induced-hereditary, being finitely determined, and being axiomatizable. We study the hom-properties of finite character, and prove some necessary and some sufficient conditions on H for →H to be of finite character. A notable (but known) sufficient condition is that H is a finite graph, and our new model-theoretic proof of this compactness result extends from hom-properties to all axiomatizable properties. In our quest to find an intrinsic characterization of those H for which →H is of finite character, we find an example of an infinite connected graph with no finite core and chromatic number 3 but with hom-property not of finite character.
- Published
- 2016
- Full Text
- View/download PDF
46. A dynamic domination problem in trees
- Author
-
William Klostermeyer and Christina Mynhardt
- Subjects
graph protection ,eternal domination ,domination number ,independence number ,Mathematics ,QA1-939 - Abstract
We consider a dynamic domination problem for graphs in which an infinite sequence of attacks occur at vertices with guards and the guard at the attacked vertex is required to vacate the vertex by moving to a neighboring vertex with no guard. Other guards are allowed to move at the same time, and before and after each attack and the resulting guard movements, the vertices containing guards form a dominating set of the graph. The minimum number of guards that can successfully defend the graph against such an arbitrary sequence of attacks is the m-eviction number. This parameter lies between the domination and independence numbers of the graph. We characterize the classes of trees for which the m-eviction number equals the domination number and the independence number, respectively.
- Published
- 2015
47. New Bounds for the α-Indices of Graphs
- Author
-
Eber Lenes, Exequiel Mallea-Zepeda, and Jonnathan Rodríguez
- Subjects
spectral radius ,minimal degree ,independence number ,α-adjacency matrix ,Mathematics ,QA1-939 - 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−l2⌋, let Gp≅Kl∨(Kp∪Kn−p−l) be the graph obtained from the graphs Kl and Kp∪Kn−p−l and edges connecting each vertex of Kl with every vertex of Kp∪Kn−p−l. We prove that ρα(Gp+1)<ρα(Gp) for 1≤p≤⌊n−l2⌋−1.
- Published
- 2020
- Full Text
- View/download PDF
48. On The Independence Number Of Some Strong Products Of Cycle-Powers
- Author
-
Jurkiewicz Marcin, Kubale Marek, and Ocetkiewicz Krzysztof
- Subjects
strong product ,exhaustive search algorithm ,independence number ,shannon capacity ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
In the paper we give some theoretical and computational results on the third strong power of cycle-powers, for example, we have found the independence numbers α((C102)√3) = 30 and α((C144)√3) = 14. A number of optimizations have been introduced to improve the running time of our exhaustive algorithm used to establish the independence number of the third strong power of cycle-powers. Moreover, our results establish new exact values and/or lower bounds on the Shannon capacity of noisy channels.
- Published
- 2015
- Full Text
- View/download PDF
49. Extending the MAX Algorithm for Maximum Independent Set
- Author
-
Lê Ngoc C., Brause Christoph, and Schiermeyer Ingo
- Subjects
maximum independent set ,stable set ,stability number ,independence number ,reduction ,graph transformation ,max algorithm ,min algorithm ,vertex order algorithm ,Mathematics ,QA1-939 - Abstract
The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.
- Published
- 2015
- Full Text
- View/download PDF
50. On the Independence Number of Edge Chromatic Critical Graphs
- Author
-
Pang Shiyou, Miao Lianying, Song Wenyao, and Miao Zhengke
- Subjects
edge coloring ,edge-chromatic critical graphs ,independence number ,Mathematics ,QA1-939 - Abstract
In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤. It is known that α (G) < |V |. In this paper we improve this bound when △≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α (G) ≤|V | when △ ≥ 5 and n2 ≤ 2(△− 1)
- Published
- 2014
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.