Search

Fuzzy graph models occur specifically in the dynamic processes of physical, biological, and social systems. Data transmission reliability, routing optimization, and network failure detection are all aided by connectivity analysis of fuzzy graph models. The cyclic connectivity analysis in terms of cycles in fuzzy graphs has grown into a prominent field of study. As strong cycles between vertices serve as a critical path for information flow, we propose a connectivity metric that considers the significance of strong cycles, providing a comprehensive approach in the area of connectivity. In this paper we extends the average connectivity concepts in terms of the cycles in fuzzy graphs. Also, the average cyclic connectivity of subgraphs, complete fuzzy graphs, θ -fuzzy graphs, and other related topics are examined. An algorithm for finding the new connectivity measure is provided and a practical implementation in real world scenarios is also discussed. [ABSTRACT FROM AUTHOR]

For a commutative ring R , even elements in R as vertices and two distinct vertices x i , y j ∈ R are adjacent iff x i y j = 0 or y j x i = 0 , then the graph is known as an even prime graph. In compressed even prime graph, whose vertex set is the set of all equivalence classes of even elements in R , the equivalence classes elements are denoted by [ β ] or β ¯ and two distinct equivalence classes [ β i ] and [ β j ] are adjacent iff [ β i ] [ β j ] = 0 , graph is denoted by E P G E (Z n) . This paper delves into discussions regarding the chromatic number and clique number of such graphs across various families. Additionally, we discuss the chromatic number of the prime graph associated with the commutative ring R . [ABSTRACT FROM AUTHOR]

For an edge-colored graph G, we call an edge-cut M of G monochromatic if the edges of M are colored with a same color. The graph G is called monochromatically disconnected if any two distinct vertices of G are separated by a monochromatic edge-cut. The monochromatic disconnection number, denoted by md(G), of a connected graph G is the maximum number of colors that are allowed to make G monochromatically disconnected. In this paper, we solve the Erdős-Gallai-type problems for the monochromatic disconnection, and give the monochromatic disconnection numbers for four graph products, i.e., Cartesian, strong, lexicographic, and tensor products. [ABSTRACT FROM AUTHOR]

The power graph of a group is the simple graph whose vertices are the group elements and two vertices are adjacent whenever one of them is a positive power of the other. In this paper, we characterize the finite nilpotent groups whose power graphs have equal vertex connectivity and minimum degree. [ABSTRACT FROM AUTHOR]

Identifying certain conditions that ensure the Hamiltonicity of graphs is highly important and valuable due to the fact that determining whether a graph is Hamiltonian is an NP-complete problem.For a graph G with vertex set V(G) and edge set E(G), the first Zagreb index ( M 1 ) and second Zagreb index ( M 2 ) are defined as M 1 (G) = ∑ v i v j ∈ E (G) (d G (v i) + d G (v j)) and M 2 (G) = ∑ v i v j ∈ E (G) d G (v i) d G (v j) , where d G (v i) denotes the degree of vertex v i ∈ V (G) . The difference of Zagreb indices ( Δ M ) of G is defined as Δ M (G) = M 2 (G) - M 1 (G) .In this paper, we try to look for the relationship between structural graph theory and chemical graph theory. We obtain some sufficient conditions, with regards to Δ M (G) , for graphs to be k-hamiltonian, traceable, k-edge-hamiltonian, k-connected, Hamilton-connected or k-path-coverable. [ABSTRACT FROM AUTHOR]

Kriesell (J Comb Theory Ser B 88:53–65, 2003) proposed Conjecture 1: If S ⊆ V (G) is 2k-edge-connected in a graph G, then G contains k edge-disjoint S-Steiner trees. West and Wu (J Comb Theory Ser B 102:186–205, 1961) posed Conjecture 2: If S ⊆ V (G) is 3k-edge-connected in a graph G, then G contains k edge-disjoint S-connectors, which is an analogue for S-connectors of Kriesell’s Conjecture. This paper shows If | V (G) - S | ≤ k , then Conjecture 1 is true and if | V (G) - S | ≤ 2 k , then Conjecture 2 is true. This paper also investigate the validity of two conjectures with certain additional conditions of | V (G) - S | or |S|. [ABSTRACT FROM AUTHOR]

In this paper, we consider the spectral radius of signless p-Laplacian of a graph, which is a generalization of the quadratic form of the signless Laplacian matrix for p = 2 . Let π = (d 0 , d 1 , … , d n - 1) be a non-increasing sequence of positive integers and G π the set of graphs with degree sequence π . In this paper, we obtain some transformations for graphs in G π that do not decrease the largest signless p-Laplacian eigenvalue of a graph. Furthermore, if ∑ i = 0 n - 1 d i = 2 n and d 2 ≥ 2 , then we identify the graph maximizing the signless p-Laplacian spectral radius among G π . As an application, we get the extremal graph maximizing the signless p-Laplacian spectral radius among all unicyclic graphs. [ABSTRACT FROM AUTHOR]

The conjecture of Beineke and Harary states that for any two vertices which can be separated by k vertices and l edges for l ≥ 1 but neither by k vertices and l - 1 edges nor k - 1 vertices and l edges there are k + l edge-disjoint paths connecting these two vertices of which k + 1 are internally disjoint.In this paper we prove this conjecture for l = 2 and every k ∈ N .We utilize this result to prove that the conjecture holds for all graphs of treewidth at most 3 and all k and l. [ABSTRACT FROM AUTHOR]

The Steiner tree problem in graphs is widely studied because of its usefulness in network design and circuit layout. In this context, given a set of vertices S (| S | ≥ 2 ,) a tree that connects all vertices in S is called an S-Steiner tree. This helps to measure how well a network G can connect any set of S vertices together. In an S-Steiner tree, if each vertex in S has only one connection, it is called a pendant S-Steiner tree. Two pendant S-Steiner trees, T and T ′ , are internally disjoint if E (T) ∩ E (T ′) = ∅ and V (T) ∩ V (T ′) = S. The local pendant tree-connectivity, denoted as τ G (S) , represents the maximum number of internally disjoint pendant S-Steiner trees in graph G. For an integer k with 2 ≤ k ≤ n , where n is the number of vertices, the pendant k-tree-connectivity, denoted as τ k (G) , is defined as τ k (G) = m i n { τ G (S) : S ⊆ V (G) , | S | = k }. This paper focuses on studying the pendant 3-tree-connectivity of augmented cubes, which are modified versions of hypercubes designed to enhance connectivity and reduce diameter. This research demonstrates that the pendant 3-tree-connectivity of augmented cubes, denoted as τ 3 (A Q n) is 2 n - 3 . This result matches the upper bound of τ 3 (G) provided by Hager, specifically for the augmented cube graph A Q n . [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n ≥ 2 and let k ∈ { 1 , ... , n - 1 } . 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 their symmetric difference is an edge of G. In 2018 Leaños and Trujillo-Negrete proved that if G is t-connected and t ≥ k , then F k (G) is at least k (t - k + 1) -connected. In this paper we show that such a lower bound remains true in the context of edge-connectivity. Specifically, we show that if G is t-edge-connected and t ≥ k , then F k (G) is at least k (t - k + 1) -edge-connected. We also provide some families of graphs attaining this bound. [ABSTRACT FROM AUTHOR]

A graph is called supereulerian if it has a spanning eulerian subgraph. A connected even [2, 2s]-factor of a graph G is a connected factor with all vertices of even degree i (i ∈ { 2 , 4 , … , 2 s }) , where s ≥ 1 is an integer. Let W s , t be the graph obtained from vertex-disjoint s K 2 and (t + 1) K 1 by adding all possible edges between exactly one K 1 and the remaining graphs s K 2 and t K 1 . When s = t = 1 , W 1 , 1 is Z 1 . In this paper, we show that for any positive integer k ≤ 4 and 2 ≤ i ≤ k + 1 , every connected supereulerian H -free graph of order at least 6 contains a connected even [2, 2k]-factor if and only if H satisfies the following condition. H ≼ { { K 1 , 2 k + 2 , Z 1 } , { K 1 , k + i , W k + 3 - i , 0 } , { K 1 , k + i , W k + 2 - i , i - 1 } }. And when k = 5 , 6 , we give some relevant results. We also show that for positive integers k, 2 ≤ i ≤ k + 1 and H ≼ { { K 1 , 2 k + 2 , Z 1 } , { K 1 , k + i , W k + 3 - i , 0 } } , if G is supereulerian H -free graph of order at least 6, then G contains a connected even [2, 2k]-factor. Our results extend the result of Yang et al. (Discrete Appl Math 288:192–200, 2021) and Duan et al. (Ars Comb 115:385–389, 2014). [ABSTRACT FROM AUTHOR]

Traditional centrality metrics consider only shortest paths, neglecting alternative paths that can be strategic to maintain network connectivity. This paper proposes the disjoint multipath closeness centrality, a new metric to compute node centrality that extrapolates the traditional closeness to consider multiple shortest and disjoint quasi-shortest paths. The idea is to identify nodes that are close to all other nodes and are multiply-connected, which is important to perform high availability tasks. We limit the number of multiple disjoint paths using a connectivity factor φ . We comparatively investigate the correlation between our metric, the traditional closeness, and the information centrality using social and communication networks. We also assess the node ranking obtained by each metric and evaluate node reachability when one or multiple network failures occur. The results show that our metric maintains high concordance with the other closeness metrics but it can reclassify at least 59% of nodes in the evaluated networks. Our metric indeed identifies better-connected nodes, which remain more accessible when failures happen. [ABSTRACT FROM AUTHOR]

The study of the relationships between the eigenvalues of a graph and its structural parameters is a central topic in spectral graph theory. In this paper, we give some new spectral conditions for the connectivity, toughness and perfect k-matchings of regular graphs. Our results extend or improve the previous related ones. [ABSTRACT FROM AUTHOR]

The Hamiltonian path and cycle problems are well-known NP-complete problems. A given graph is Hamiltonian-connected if there exists a Hamiltonian path between any two vertices and is Hamiltonian if it has a Hamiltonian cycle. In this paper, we show that every 3-connected solid supergrid graph is Hamiltonian-connected and every 2-connected solid supergrid graph is Hamiltonian, and give linear-time algorithms for computing Hamiltonian cycles and paths in these graphs. [ABSTRACT FROM AUTHOR]

A k-connected (resp. k-edge-connected) edge dominating set D of a connected graph G is a subset of E(G) such that G[D] is k-connected (resp. k-edge-connected) and each e ∈ E (G) \ D has at least one neighbor in D. The k-connected edge domination number (resp. k-edge-connected edge domination number) of a graph G is the minimum size of a k-connected (resp. k-edge-connected) edge dominating set of G, and denoted by γ k (G) (resp. γ k ′ (G) ). In this paper, we investigate the relationship between matching number and 2-connected (resp. 2-edge-connected) edge domination number, and prove that for a graph G, if it is 2-edge-connected, then γ 2 ′ (G) ≤ 5 α ′ (G) - 2 , and if it is 2-connected, then γ 2 (G) ≤ 4 α ′ (G) - 1 , where α ′ (G) is the matching number of G. [ABSTRACT FROM AUTHOR]

The concept of rainbow disconnection number of graphs was introduced by Chartrand et al. (2018). Inspired by this concept, we put forward the concepts of rainbow vertex-disconnection and proper disconnection in graphs. In this paper, we first show that it is NP-complete to decide whether a given edge-colored graph G has a proper edge-cut separating two specified vertices, even though the graph G has Δ (G) = 4 or is bipartite. Then, for a graph G with Δ (G) ≤ 3 we show that p d (G) ≤ 2 and distinguish the graphs with p d (G) = 1 and 2, respectively. We also show that it is NP-complete to decide whether a given vertex-colored graph G is rainbow vertex-disconnected, even though the graph G has Δ (G) = 3 or is bipartite. [ABSTRACT FROM AUTHOR]

Let G be an irregular graph on n vertices with maximum degree Δ ≥ 3 and diameter D ≥ 3 . The spectral radius of G, which is denoted by ρ (G) , is the largest eigenvalue of the adjacency matrix of G. In this paper, a new lower bound of Δ - ρ (G) is given, which improves the previous bounds intrinsically. [ABSTRACT FROM AUTHOR]

Let G be a nontrivial connected and vertex-colored graph. A vertex subset X is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G - S ; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of (G - x y) - S . For a connected graph G, the rainbow vertex-disconnection number of G, rvd(G), is the minimum number of colors that are needed to make G rainbow vertex-disconnected. In this paper, we prove for any K 4 -minor free graph, r v d (G) ≤ Δ (G) and the bound is sharp. We show it is NP-complete to determine the rainbow vertex-disconnection numbers for bipartite graphs and split graphs. Moreover, we show for every ϵ > 0 , it is impossible to efficiently approximate the rainbow vertex-disconnection number of any bipartite graph and split graph within a factor of n 1 3 - ϵ unless Z P P = N P . [ABSTRACT FROM AUTHOR]

Given a finite point set P in general position in the plane, a full triangulation of P is a maximal straight-line embedded plane graph on P. A partial triangulation of P is a full triangulation of some subset P ′ of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge (called edge flip), removes a non-extreme point of degree 3, or adds a point in P \ P ′ as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For sets P of n points in the plane in general position, we show that the edge flip graph is ⌈ n / 2 - 2 ⌉ -vertex connected, and the bistellar flip graph is (n - 3) -vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where (n - 3) -vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski's Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided that n is large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension ⌈ n / 2 - 2 ⌉ (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension n - 3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n - 3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height n - 3 . (iv) There are arbitrarily large sets P with non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations. [ABSTRACT FROM AUTHOR]

Given a connected graph G with vertex set V G , a subset I of V G is called independent if there are no edges between any two vertices from I. Let i k (G) be the number of independent sets with cardinality k of G and let i 0 (G) = 1 . The independence polynomial of G is defined as I (G ; x) = ∑ k ⩾ 0 i k (G) x k , where i (G) = I (G ; 1) is called the Merrifield–Simmons index of G. In this paper, some extremal problems on the coefficients of the independence polynomial of bipartite graphs are considered. Firstly, the second largest i k (G) (k ⩾ 2) among all bipartite graphs is determined, and the graph which simultaneously minimizes all coefficients of I(G; x) among all bipartite graphs is characterized. Secondly, the largest i k (G) (k ⩾ 2) among all bipartite graphs with at least one cycle is determined, and the unique graph which minimizes all coefficients of I(G; x) among all bipartite graphs with given matching number (resp. diameter at most four, connectivity) is characterized as well. [ABSTRACT FROM AUTHOR]

A path in a vertex-coloured graph is called conflict-free if there is a colour used on exactly one of its vertices. A vertex-coloured graph is said to be conflict-free vertex-connected if any two distinct vertices of the graph are connected by at least one conflict-free vertex-path. The conflict-free vertex-connection number, denoted by vcfc(G), is the smallest number of colours needed in order to make G conflict-free vertex-connected. Our main result of this paper is the following: Let G be a connected graph of order n ≥ 11 . If δ (G) ≥ n 5 , then v c f c (G) ≤ 3 . Moreover, we show that both bounds, on the order n and the minimum degree δ (G) , are tight. Furthermore, we generalize our result by requiring minimum degree-sum conditions for pairs, triples or quadruples of independent vertices. [ABSTRACT FROM AUTHOR]

A vertex-colored path P is rainbow if its internal vertices have distinct colors; whereas P is monochromatic if its internal vertices are colored the same. For a vertex-colored connected graph G, the rainbow vertex-connection number rvc(G) is the minimum number of colors used such that there is a rainbow path joining any two vertices of G; whereas the monochromatic vertex-connection number mvc(G) is the maximum number of colors used such that any two vertices of G are connected by a monochromatic path. These two opposite concepts are the vertex-versions of rainbow connection number rc(G) and monochromatic connection number mc(G) respectively. The study on rc(G) and mc(G) of random graphs drew much attention, and there are few results on the rainbow and monochromatic vertex-connection numbers. In this paper, we consider these two vertex-connection numbers of random graphs and establish sharp threshold functions for them, respectively. [ABSTRACT FROM AUTHOR]

A connected hypergraph H is maximally edge (resp. vertex)-connected if the edge (resp. vertex)-connectivity attains its minimum degree. A hypergraph H is super edge (resp. vertex)-connected if every minimum edge (resp. vertex) cut isolates a vertex of H. In this paper, sufficient conditions for the Cartesian product of hypergraphs to be maximally edge-connected, super edge-connected, maximally vertex-connected, and super vertex-connected are presented. As a corollary, we deduce that the n-dimensional r-uniform cube-hypergraph Q(n, r) is both super edge-connected and super vertex-connected. [ABSTRACT FROM AUTHOR]

Given a graph G (with multiple edges allowed), a k-restricted edge-cut of G is an edge-cut R ⊆ E (G) of G such that every connected component in G - R has order at least k. A graph G is λ k -connected if k-restricted edge cuts exist. Given an edge-coloring of G, an edge-cut of G will be called heterochromatic if all its edges receive different colors. Given a graph G and an integer k ≥ 2 , let h(G, k) be the minimum integer p such that every p-coloring of the edges of G produces an heterochromatic k-restricted edge-cut of G. In this paper we prove that for a λ k -connected graph G of size m, order n ≥ 3 k - 2 , and with no k-restricted edge-cut of size 1, we have that m - n + min { κ 0 (G) - 2 , t (G , k) } + 2 ≤ h (G , k) ≤ m - n + t (G , k) + 2 , where κ 0 (G) is the vertex-connectivity of G and t(G, k) is the maximum cardinality of a set S ⊆ V (G) such that the connected components in G[S] have order at most k - 1 . As a corollary we see that h (G , k) ≤ m - n + α (G) (k - 1) + 2 , with α (G) the independence number of G. [ABSTRACT FROM AUTHOR]

Let k be an integer such that k ≥ 3. Let H k denote the set of k-connected graphs each G of which has a vertex x such that G - x is a (k - 1) -connected (k - 1) -regular graph. Note that H 3 is the set of wheels. Let G be a k-connected graph where k ≥ 2 is an integer. An operation on G is defined as follows. (I) Delete a vertex x of degree at least 2 (k - 1) from G, (II) Add new two vertices x 1 and x 2 , (III) Join x i to N i ∪ { x 3 - i } for i = 1 , 2 where N G (x) = N 1 ∪ N 2 , | N i | ≥ k - 1 for i = 1 , 2 and N 1 ∩ N 2 = ∅. We call this operation “proper vertex-splitting”. Two edges of a graph are said to be “independent” if they have no common end vertex and a set of edges is said to be “independent” if each two of it are independent. Let G be a 2k-connected graph where k is a positive integer. We define an operation on G as follows. (I) Choose independent k edges of G, (II) Subdivide each of the chosen k edges by one vertex, (III) Identify the new k vertices arising from the subdivisions. We call this operation “edge-binding”. Tutte gave a constructive characterization of 3-connected graphs. Theorem (Tutte’s wheel theorem, 1961) Every 3-connected graph can be obtained from a graph in H 3 by repeated applications of edge addings and proper vertex-splittings. In this paper we prove the following 4-connected analogue of Tutte’s Wheel Theorem. Theorem Every 4-connected graph can be obtained from a graph in H 4 by repeated applications of edge addings, proper vertex-splittings and edge-bindings. [ABSTRACT FROM AUTHOR]

Let G be a finite abelian group, written additively, and H a subgroup of G. The subgroup sum graph Γ G , H is the graph with vertex set G, in which two distinct vertices x and y are joined if x + y ∈ H \ { 0 } . These graphs form a fairly large class of Cayley sum graphs. Among cases which have been considered previously are the prime sum graphs, in the case where H = p G for some prime number p. In this paper we present their structure and a detailed analysis of their properties. We also consider the simpler graph Γ G , H + , which we refer to as the extended subgroup sum graph, in which x and y are joined if x + y ∈ H : the subgroup sum is obtained by removing from this graph the partial matching of edges having the form { x , - x } when 2 x ≠ 0 . We study perfectness, clique number and independence number, connectedness, diameter, spectrum, and domination number of these graphs and their complements. We interpret our general results in detail in the prime sum graphs. [ABSTRACT FROM AUTHOR]

A graph is called 1-planar if it can be drawn on the plane (or on the sphere) such that each edge is crossed at most once. It is known that a 1-planar graph G with at least three vertices has at most 4 | V (G) | - 8 edges, so G is optimal if G has exactly 4 | V (G) | - 8 edges. The vertex-connectivity of an optimal 1-planar graph has been proven to be either 4 or 6. According to the Whitney inequality, the edge-connectivity of an optimal 1-planar graph is at least 4. In this paper, we provide a more precise result. We prove that the edge-connectivity of every optimal 1-planar graph is 6. Additionally, we prove that any minimum edge-cut of an optimal 1-planar graph is a set of all the edges incident with a vertex of degree 6. In addition, we prove that an optimal 1-planar graph has the restricted edge-connectivity 8, 10 or 12. [ABSTRACT FROM AUTHOR]

An edge-colored graph is called rainbow if every two edges receive distinct colors, and called proper if every two adjacent edges receive distinct colors. An edge-colored graph G c is properly vertex/edge-pancyclic if every vertex/edge of the graph is contained in a proper cycle of length k for every k with 3 ≤ k ≤ | V (G) | . A triangle C of G c is called a 2-triangle if C receives exactly two colors. We call G c 2-triangle-free if G c contains no 2-triangle. Let d c (v) be the number of colors on the edges incident to v in G c and let δ c (G) be the minimum d c (v) over all the vertices v ∈ V (G c) . We show in this paper that: (i) a 2-triangle-free edge-colored complete graph K n c is properly vertex-pancyclic if δ c (K n) ≥ ⌈ n 3 ⌉ + 1 , and is properly edge-pancyclic if δ c (K n) ≥ ⌈ n 3 ⌉ + 2 . (ii) with the exception of a few edge-colored graphs on at most 9 vertices, every vertex of a 2-triangle-free edge-colored complete graph K n c with δ c (K n) ≥ 4 is contained in a rainbow C 4 ; (iii) every vertex of a 2-triangle-free edge-colored complete graph K n c with δ c (K n) ≥ 5 is contained in a rainbow C 5 unless G is proper or G is a special edge-colored K 8 . [ABSTRACT FROM AUTHOR]

Let G be a vertex-colored connected graph. A subset U of the vertex set of G is called monochromatic, if all vertices of U are assigned the same color. The vertex-colored graph G is called monochromatic vertex-disconnected if for any two distinct vertices x and y, there is a monochromatic vertex-subset S of G such that x and y belong to different components of G - S if x and y are nonadjacent, and if x and y are adjacent, then x or y has the same color as S and x and y belong to distinct components of (G - x y) - S . The monochromatic vertex-disconnection number of a connected graph G, denoted by mvd (G) , is defined as the maximum number of colors that are allowed to make G monochromatic vertex-disconnected. The concept is inspired by the concepts of rainbow vertex-disconnection number rvd (G) and monochromatic disconnection number md (G) . In this paper, we present some sufficient conditions for a connected graph G to have mvd (G) = 1 and show that almost all graphs have monochromatic vertex-disconnection number 1. Moreover, we present Nordhaus–Gaddum-type results for the new parameter mvd (G) . At last, we investigate the monochromatic vertex-disconnection numbers for four graph products. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V and let b > a be two positive integers. We say that G has all [a, b]-factors if G has an h-factor for every h : V → N such that a ≤ h (v) ≤ b for every v ∈ V and ∑ v ∈ V h (v) ≡ 0 (mod 2) . A spanning subgraph F of G is called an (a, b)-parity factor, if d F (v) ≡ a ≡ b (mod 2) and a ≤ d F (v) ≤ b for all v ∈ V . In this paper, we have developed sufficient conditions for the existence of all [a, b]-factors and (a, b)-parity factors of G in terms of the independence number and connectivity of G. This work extended an earlier result of Nishimura (J Graph Theory 13: 63–69, 1989). Furthermore, we show that these results are best possible in some cases. [ABSTRACT FROM AUTHOR]

Graph invariants provide an outstanding tool for investigation of abstract structures of graphs. They contain global and general information about a graph and its particular substructures. In this paper, the graph invariants such as vertex connectivity, metric dimension, minimum vertex degree, independence number, domination number, Laplacian energy and Zagreb indices of line graph of zero-divisor graph over the rings Z pq and Z p n (where p and q are prime) are determined. Moreover, we provide a MATLAB code for calculating Laplacian energy and Zagreb indices of line graph of Γ (Z n) . [ABSTRACT FROM AUTHOR]

A graph is called Hamilton-connected if there exists a Hamiltonian path between every pair of its vertices. Determining whether or not a graph is Hamilton-connected is an NP-complete problem. In this paper, we present two methods to show Hamilton-connectivity in graphs. The first method uses the vertex connectivity and Hamiltoniancity of graphs, and, the second is the definition-based constructive method which constructs Hamiltonian paths between every pair of vertices. By employing these proof techniques, we show that the line graphs of the generalized Petersen, anti-prism and wheel graphs are Hamilton-connected. Combining it with some existing results, it shows that some of these families of Hamilton-connected line graphs have their underlying graph families non-Hamilton-connected. This, in turn, shows that the underlying graph of a Hamilton-connected line graph is not necessarily Hamilton-connected. As side results, the detour index being also an NP-complete problem, has been calculated for the families of Hamilton-connected line graphs. Finally, by computer we generate all the Hamilton-connected graphs on ≤ 7 vertices and all the Hamilton-laceable graphs on ≤ 10 vertices. Our research contributes towards our proposed conjecture that almost all graphs are Hamilton-connected. [ABSTRACT FROM AUTHOR]

For a digraph D = (V (D) , A (D)) , and a set S ⊆ V (D) with r ∈ S and | S | ≥ 2 , an (S, r)-tree is an out-tree T rooted at r with S ⊆ V (T) . Two (S, r)-trees T 1 and T 2 are said to be arc-disjoint if A (T 1) ∩ A (T 2) = ∅ . Two arc-disjoint (S, r)-trees T 1 and T 2 are said to be internally disjoint if V (T 1) ∩ V (T 2) = S . Let κ S , r (D) and λ S , r (D) be the maximum number of internally disjoint and arc-disjoint (S, r)-trees in D, respectively. The generalized k-vertex-strong connectivity of D is defined as κ k (D) = min { κ S , r (D) ∣ S ⊆ V (D) , | S | = k , r ∈ S }. Similarly, the generalized k-arc-strong connectivity of D is defined as λ k (D) = min { λ S , r (D) ∣ S ⊆ V (D) , | S | = k , r ∈ S }. The generalized k-vertex-strong connectivity and generalized k-arc-strong connectivity are also called directed tree connectivity which could be seen as a generalization of classical connectivity of digraphs and a natural extension of undirected tree connectivity. A digraph D = (V (D) , A (D)) is called minimally generalized (k , ℓ) -vertex (respectively, arc)-strongly connected if κ k (D) ≥ ℓ (respectively, λ k (D) ≥ ℓ ) but for any arc e ∈ A (D) , κ k (D - e) ≤ ℓ - 1 (respectively, λ k (D - e) ≤ ℓ - 1 ). In this paper, we study the minimally generalized (k , ℓ) -vertex (respectively, arc)-strongly connected digraphs. We compute the minimum and maximum sizes of these digraphs and give characterizations of such digraphs for some pairs of k and ℓ . [ABSTRACT FROM AUTHOR]

An edge-cut of an edge-colored connected graph is called a rainbow cut if no two edges in the edge-cut are colored the same. An edge-colored graph is rainbow disconnected if for any two distinct vertices u and v of the graph, there exists a rainbow cut separating u and v. For a connected graph G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors required to make G rainbow disconnected. In this paper, we first give some upper bounds for rd(G), and moreover, we completely characterize the graphs which meet the upper bounds of the Nordhaus—Gaddum type result obtained early by us. Secondly, we propose a conjecture that for any connected graph G, either rd(G) = λ+(G) or rd(G) = λ+(G)+1, where λ+(G) is the upper edge-connectivity, and prove that the conjecture holds for many classes of graphs, which supports this conjecture. Moreover, we prove that for an odd integer k, if G is a k-edge-connected k-regular graph, then χ′(G) = k if and only if rd(G) = k. It implies that there are infinitely many k-edge-connected k-regular graphs G for which rd(G)= λ+(G)for odd k, and also there are infinitely many k-edge-connected k-regular graphs G for which rd(G)= λ+(G) + 1 for odd k. For k = 3, the result gives rise to an interesting result, which is equivalent to the famous Four-Color Problem. Finally, we give the relationship between rd(G) of a graph G and the rainbow vertex-disconnection number rvd(L(G)) of the line graph L(G) of G. [ABSTRACT FROM AUTHOR]

A graph is said to be total-colored if all the edges and the vertices of the graph are colored. A path P in a total-colored graph G is called a total-proper path if (1) any two adjacent edges of P are assigned distinct colors; (2) any two adjacent internal vertices of P are assigned distinct colors; and (3) any internal vertex of P is assigned a distinct color from its incident edges of P. The total-colored graph G is total-proper connected if any two distinct vertices of G are connected by a total-proper path. The total-proper connection number of a connected graph G, denoted by tpc(G), is the minimum number of colors that are required to make G total-proper connected. In this paper, we first characterize the graphs G on n vertices with tpc(G)=n-1. Based on this, we obtain a Nordhaus-Gaddum-type result for total-proper connection number. We prove that if G and G¯ are connected complementary graphs on n vertices, then 6≤tpc(G)+tpc(G¯)≤n+2. Examples are given to show that the lower bound is sharp for n≥4. The upper bound is reached for n≥4 if and only if G or G¯ is the tree with maximum degree n-2. [ABSTRACT FROM AUTHOR]

Let G be a graph and k an integer with 2 ≤ k ≤ n . The k-tree-connectivity of G, denoted by κ k (G) , is defined as the minimum κ G (S) over all k-subsets S of vertices, where κ G (S) denotes the maximum number of internally disjoint S-trees in G. The k-path-connectivity of G, denoted by π k (G) , is defined as the minimum π G (S) over all k-subsets S of vertices, where π G (S) denotes the maximum number of internally disjoint S-paths in G. In this paper, we first prove that for any fixed integer k ≥ 1 , given a graph G and a subset S of V(G), deciding whether π G (S) ≥ k is NP -complete. Moreover, we also show that for any fixed integer k 1 ≥ 5 , given a graph G, a k 1 -subset S of V(G) and an integer 1 ≤ k 2 ≤ n - 1 , deciding whether π G (S) ≥ k 2 is NP -complete. Let π (k , ℓ) = 1 + max { κ (G) | G \ is\ a\ graph\ with π k (G) < ℓ } . Hager (Discrete Math 59:53–59, 1986) showed that ℓ (k - 1) ≤ π (k , ℓ) ≤ 2 k - 2 ℓ and conjectured that π (k , ℓ) = ℓ (k - 1) for k ≥ 2 and ℓ ≥ 1 . He also confirmed the conjecture for 2 ≤ k ≤ 4 and proved π (5 , ℓ) ≤ ⌈ 9 2 ℓ ⌉ . By introducing a "Generalized Path-Bundle Transformation", we confirm the conjecture for k = 5 and prove that π (k , ℓ) ≤ 2 k - 3 ℓ for k ≥ 5 and ℓ ≥ 1 . By employing this transformation, we also prove that if G is a graph with κ (G) ≥ (k - 1) ℓ for any k ≥ 2 and ℓ ≥ 1 , then κ k (G) ≥ ℓ . [ABSTRACT FROM AUTHOR]

Let G be an edge-colored connected graph. A path P in G is called ℓ -rainbow if no two edges of the same color have fewer than ℓ edges between them on P. The graph G is called (k , ℓ) -rainbow connected if every pair of distinct vertices of G are connected by k pairwise internally vertex-disjoint ℓ -rainbow paths in G. For a k-connected graph G, the minimum number of colors needed to make G (k , ℓ) -rainbow connected is called the (k , ℓ) -rainbow connection number of G and denoted by r c k , ℓ (G) . In this paper, we prove that r c 1 , 2 (G) ≤ 5 for any 2-connected graph G and provide a counter example which overturns a conjecture posed by Chartrand et al. in 2016. Considering graph operations, we study the (1, 2)-rainbow connection numbers for the join, the Cartesian, strong and lexicographic products of graphs, giving the sharp upper bounds for nearly all graph products. In addition, we find some basic properties of the (k , ℓ) -rainbow connection number and determine the values of r c 1 , ℓ (G) where G is a cube or a permutation graph of a nontrivial traceable graph. [ABSTRACT FROM AUTHOR]

A vertex-colored graph G is rainbow vertex connected if any two distinct vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex connection number of G, denoted by rvc( G), is the smallest number of colors that are needed in order to make G rainbow vertex connected. In this paper, we prove that for a connected graph G, if $${{\rm diam}(\overline{G}) \geq 3}$$ , then $${{\rm rvc}(G) \leq 2}$$ , and this bound is tight. Next, we obtain that for a triangle-free graph $${\overline{G}}$$ with $${{\rm diam}(\overline{G}) = 2}$$ , if G is connected, then $${{\rm rvc}(G) \leq 2}$$ , and this bound is tight. A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc( G), is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we prove that for a triangle-free graph $${\overline{G}}$$ with $${{\rm diam}(\overline{G}) = 3}$$ , if G is connected, then trc $${(G) \leq 5}$$ , and this bound is tight. Next, a Nordhaus-Gaddum-type result for the total rainbow connection number is provided. We show that if G and $${\overline{G}}$$ are both connected, then $${6 \leq {\rm trc} (G) + {\rm trc}(\overline{G}) \leq 4n - 6.}$$ Examples are given to show that the lower bound is tight for $${n \geq 7}$$ and n = 5. Tight lower bounds are also given for n = 4, 6. [ABSTRACT FROM AUTHOR]

Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G - S ; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of (G - x y) - S . Such a vertex subset S is called an x–yrainbow vertex-cut of G. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertex-disconnected. In this paper, we obtain bounds of the rainbow vertex-disconnection number of a graph in terms of the minimum degree and maximum degree of the graph. We give a tighter upper bound for the maximum size of a graph G with r v d (G) = k for k ≥ n 2 . We then characterize the graphs of order n with rainbow vertex-disconnection number n - 1 and obtain the maximum size of a graph G with r v d (G) = n - 1 . Moreover, we get a sharp threshold function for the property r v d (G (n , p)) = n and prove that almost all graphs G have r v d (G) = r v d (G ¯) = n . Finally, we obtain some Nordhaus–Gaddum-type results: n - 5 ≤ r v d (G) + r v d (G ¯) ≤ 2 n and n - 1 ≤ r v d (G) · r v d (G ¯) ≤ n 2 for the rainbow vertex-disconnection numbers of nontrivial connected graphs G and G ¯ with order n ≥ 24 . [ABSTRACT FROM AUTHOR]

The k-rainbow index r x k (G) of a connected graph G was introduced in 2010. As a natural counterpart of the k-rainbow index, the concept of k-vertex-rainbow index r v x k (G) of a connected graph G was introduced in 2016. In this paper, we mainly investigate the k-vertex-rainbow index of a connected graph G and obtain some sharp bounds for r v x k (G) . In particular, by using Lovasz Local Lemma and dominating sets, we prove that a connected graph G with n vertices and minimum degree δ has r v x 3 (G) < 11 n δ + 16 . In general, the investigation of k-vertex-rainbow index of a graph may be harder than that of k-rainbow index of a graph. For example, it is noticed that r x 2 (G) ≤ r x 3 (G) ≤ ⋯ ≤ r x n (G) for every connected graph G of order n, but we show that this monotonicity of vertex-rainbow index does not hold in some graph classes by illustrating a counterexample which is a cycle of order n. As a byproduct, we get the exact values of k-vertex-rainbow index for a cycle of order n when k = 3 , n - 4 , n - 3 , n - 2 , n - 1 and n, respectively. [ABSTRACT FROM AUTHOR]

A path P in an edge-colored graph G is called a proper path if no two adjacent edges of P are colored the same, and G is proper connected if every two vertices of G are connected by a proper path in G. The proper connection number of a connected graph G, denoted by pc(G), is the minimum number of colors that are needed to make G proper connected. In this paper, we study the proper connection number on the lexicographic, strong, Cartesian, and direct products and present exact values or upper bounds for these products of graphs. [ABSTRACT FROM AUTHOR]

We study the classical NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MAXEDP) or node-disjoint paths (MAXNDP) in a given graph. The approximability of MAXEDP/MAXNDP is currently not well understood; the best known lower bound is 2Ω(logn), assuming NP⊈DTIME(nO(logn)). This constitutes a significant gap to the best known approximation upper bound of O(n) due to Chekuri et al. (Theory Comput 2:137-146, 2006), and closing this gap is currently one of the big open problems in approximation algorithms. In their seminal paper, Raghavan and Thompson (Combinatorica 7(4):365-374, 1987) introduce the technique of randomized rounding for LPs; their technique gives an O(1)-approximation when edges (or nodes) may be used by Ologn/loglogn paths. In this paper, we strengthen the fundamental results above. We provide new bounds formulated in terms of the feedback vertex set numberr of a graph, which measures its vertex deletion distance to a forest. In particular, we obtain the following results:For MAXEDP, we give an O(rlog(kr))-approximation algorithm. Up to a logarithmic factor, our result strengthens the best known ratio O(n) due to Chekuri et al., as r≤n.Further, we show how to route Ω(OPT∗) pairs with congestion bounded by O(log(kr)/loglog(kr)), strengthening the bound obtained by the classic approach of Raghavan and Thompson.For MAXNDP, we give an algorithm that gives the optimal answer in time (k+r)O(r)·n. This is a substantial improvement on the run time of 2krO(r)·n, which can be obtained via an algorithm by Scheffler. We complement these positive results by proving that MAXEDP is NP-hard even for r=1, and MAXNDP is W[1]-hard when r is the parameter. This shows that neither problem is fixed-parameter tractable in r unless FPT=W[1] and that our approximability results are relevant even for very small constant values of r. [ABSTRACT FROM AUTHOR]

For an edge-colored graph G, a set F of edges of G is called a proper edge-cut if F is an edge-cut of G and any pair of adjacent edges in F are assigned different colors. An edge-colored graph is proper disconnected if for each pair of distinct vertices of G there exists a proper edge-cut separating them. For a connected graph G, the proper disconnection number of G, denoted by pd(G), is the minimum number of colors that are needed in order to make G proper disconnected. In this paper, we first give the exact values of the proper disconnection numbers for some special families of graphs. Next, we obtain a sharp upper bound of pd(G) for a connected graph G of order n, i.e, p d (G) ≤ min { χ ′ (G) - 1 , n 2 } . Finally, we show that for given integers k and n, the minimum size of a connected graph G of order n with p d (G) = k is n - 1 for k = 1 and n + 2 k - 4 for 2 ≤ k ≤ ⌈ n 2 ⌉ . [ABSTRACT FROM AUTHOR]

Let G be a connected irregular graph on n vertices with maximum degree Δ and diameter D. The spectral radius of G, which is denoted by ρ (G) , is the largest eigenvalue of the adjacency matrix of G. In this paper, we study the lower bound of Δ - ρ (G) . As a result, a new lower bound is obtained which improves the known lower bounds of Δ - ρ (G) . [ABSTRACT FROM AUTHOR]

An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path, which contains a color used on exactly one of its edges. The conflict-free connection number of a connected graph G, denoted by cfc(G), is defined as the minimum number of colors that are required in order to make G conflict-free connected. In this paper, we investigate the relation between the conflict-free connection number and the independence number of a graph. We firstly show that cfc(G) ≤ α(G) for any connected graph G, and give an example to show that the bound is sharp. With this result, we prove that if T is a tree with Δ (T) ≥ α (T) + 2 2 , then cfc(T) = Δ(T). [ABSTRACT FROM AUTHOR]

Peter Cameron introduced the concept of the circular altitude of graphs, a parameter which was shown by Bamberg et al. that provides a lower bound on the circular chromatic number. In this paper, we investigate this parameter and show that the circular altitude of a graph is equal to the maximum of circular altitudes of its blocks. Also, we show that homomorphically equivalent graphs have the same circular altitudes. Finally, we prove that the circular altitude of the Cartesian product of two graphs is equal to the maximum of circular altitudes of its factors. [ABSTRACT FROM AUTHOR]

Let G be a nontrivial connected graph with a vertex-coloring c: V (G) → { 1 , 2 , ... , q } , q ∈ N . For a set S ⊆ V (G) and | S | ≥ 2 , a subtree T of G satisfying S ⊆ V (T) is said to be an S-Steiner tree or simply S-tree. The S-tree T is called a vertex-rainbow S-tree if the vertices of V (T) \ S have distinct colors. Let k be a fixed integer with 2 ≤ k ≤ | V (G) | , if every k-subset S of V(G) has a vertex-rainbow S-tree, then G is said to be vertex-rainbow k-tree connected. The k-vertex-rainbow index of G, denoted by r v x k (G) , is the minimum number of colors that are needed in order to make G vertex-rainbow k-tree connected. In this paper, we study the 3-vertex-rainbow index of unicyclic graphs and complementary graphs, respectively. [ABSTRACT FROM AUTHOR]

In this paper we investigate some reliability measures, including super-connectivity, cyclic edge connectivity, etc., in the folded hypercubes. [ABSTRACT FROM AUTHOR]

Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G − S; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of (G − xy) − S. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertex-disconnected. In this paper, we characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G)= k for given integers k and n with 1 ≤ k ≤ n. [ABSTRACT FROM AUTHOR]

In this paper, we present sufficient conditions on eccentric connectivity index, eccentric distance sum and connective eccentricity index for graphs to be k-hamiltonian, k-edge-hamiltonian or k-path-coverable. [ABSTRACT FROM AUTHOR]