Results 11 to 20 of about 590 (74)
Weak and Strong Reinforcement Number For a Graph [PDF]
, 2010 Introducing the weak reinforcement number which is the minimum number of added edges to reduce the weak dominating number, and giving some boundary of this new parameter and ...
DOGAN, Derya +2 more
core +1 more source
The Minimum Size of a Graph with Given Tree Connectivity
Discussiones Mathematicae Graph Theory, 2021 For a graph G = (V, E) and a set S ⊆ V of at least two vertices, an S-tree is a such subgraph T of G that is a tree with S ⊆ V (T). Two S-trees T1 and T2 are said to be internally disjoint if E(T1) ∩ E(T2) = ∅ and V (T1) ∩ V (T2) = S, and edge-disjoint ...
Sun Yuefang, Sheng Bin, Jin Zemin
doaj +1 more source
The Vertex-Rainbow Connection Number of Some Graph Operations
Discussiones Mathematicae Graph Theory, 2021 A path in an edge-colored (respectively vertex-colored) graph G is rainbow (respectively vertex-rainbow) if no two edges (respectively internal vertices) of the path are colored the same.
Li Hengzhe, Ma Yingbin, Li Xueliang
doaj +1 more source
Conflict-Free Vertex-Connections of Graphs
Discussiones Mathematicae Graph Theory, 2020 A path in a vertex-colored graph is called conflict-free if there is a color used on exactly one of its vertices. A vertex-colored graph is said to be conflict-free vertex-connected if any two vertices of the graph are connected by a conflict-free path ...
Li Xueliang +5 more
doaj +1 more source
Discussiones Mathematicae Graph Theory, 2021 Let G be a 4-connected graph G, and let Ec(G) denote the set of 4-contractible edges of G. We prove results concerning the distribution of edges in Ec(G). Roughly speaking, we show that there exists a set K0 and a mapping φ : K0 → Ec(G) such that |φ −1(e)
Nakamura Shunsuke
doaj +1 more source
Old and new generalizations of line graphs
International Journal of Mathematics and Mathematical Sciences, Volume 2004, Issue 29, Page 1509-1521, 2004., 2004 Line graphs have been studied for over seventy years. In 1932, H. Whitney showed that for connected graphs, edge‐isomorphism implies isomorphism except for K3 and K1,3. The line graph transformation is one of the most widely studied of all graph transformations.
Jay Bagga
wiley +1 more source
Least eigenvalue of the connected graphs whose complements are cacti
Open Mathematics, 2019 Suppose that Γ is a graph of order n and A(Γ) = [ai,j] is its adjacency matrix such that ai,j is equal to 1 if vi is adjacent to vj and ai,j is zero otherwise, where 1 ≤ i, j ≤ n.
Wang Haiying +4 more
doaj +1 more source
A measure of graph vulnerability: scattering number
International Journal of Mathematics and Mathematical Sciences, Volume 30, Issue 1, Page 1-8, 2002., 2002 The scattering number of a graph G, denoted sc(G), is defined by sc(G) = max{c(G − S) − |S| : S⫅V(G) and c(G − S) ≠ 1} where c(G − S) denotes the number of components in G − S. It is one measure of graph vulnerability. In this paper, general results on the scattering number of a graph are considered.
Alpay Kirlangiç
wiley +1 more source
On the acyclic point‐connectivity of the n‐cube
International Journal of Mathematics and Mathematical Sciences, Volume 5, Issue 4, Page 737-744, 1982., 1982 The acyclic point‐connectivity of a graph G, denoted α(G), is the minimum number of points whose removal from G results in an acyclic graph. In a 1975 paper, Harary stated erroneously that α(Qn) = 2n−1 − 1 where Qn denotes the n‐cube. We prove that for n > 4, 7 · 2n−4 ≤ α(Qn) ≤ 2n−1 − 2n−y−2, where y = [log2(n − 1)].
John Banks, John Mitchem
wiley +1 more source
Minimum Edge Cuts in Diameter 2 Graphs
Discussiones Mathematicae Graph Theory, 2019 Plesnik proved that the edge connectivity and minimum degree are equal for diameter 2 graphs. We provide a streamlined proof of this fact and characterize the diameter 2 graphs with a nontrivial minimum edge cut.
Bickle Allan, Schwenk Allen
doaj +1 more source