Results 21 to 30 of about 101 (95)
Some Remarks on λp,q-Connectedness [PDF]
, 2007 A connected graph is λp,q-connected if there is a set of edges whose deletion leaves two components of order at least p and q, respectively. In this paper we present some sufficient conditions for graphs to be λp,q-connected.
Rautenbach, Dieter +3 more
core +1 more source
Cyclic sums, network sharing, and restricted edge cuts in graphs with long cycles [PDF]
, 2007 Cyclic Sums, Network Sharing and Restricted Edge Cuts in Graphs with Long Cycles Dieter Rautenbach , Lutz Volkmann Preprint series: 07-06, 8 MSC 2000 05A17 Partitions of integers 05C40 Connectivity Abstract We study graphs G = (V,E ...
Rautenbach, Dieter, Volkmann, Lutz
core +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
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
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
Proper Rainbow Connection Number of Graphs
Discussiones Mathematicae Graph Theory, 2021 A path in an edge-coloured graph is called a rainbow path if its edges receive pairwise distinct colours. An edge-coloured graph is said to be rainbow connected if any two distinct vertices of the graph are connected by a rainbow path.
Doan Trung Duy, Schiermeyer Ingo
doaj +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
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
On the Connectivity of Token Graphs of Trees [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Let $k$ and $n$ be integers such that $1\leq k \leq n-1$, and let $G$ be a simple graph of order $n$. The $k$-token graph $F_k(G)$ of $G$ is the graph whose vertices are the $k$-subsets of $V(G)$, where two vertices are adjacent in $F_k(G)$ whenever ...
Ruy Fabila-Monroy +2 more
doaj +1 more source
Rainbow Connection Number of Graphs with Diameter 3
Discussiones Mathematicae Graph Theory, 2017 A path in an edge-colored graph G is rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer k for which there exists a k-edge-coloring of G such that every pair of distinct vertices of G
Li Hengzhe, Li Xueliang, Sun Yuefang
doaj +1 more source