Search

It is a well-known fact that a graph of diameter d has at least d + 1 eigenvalues (A.E. Brouwer, W.H. Haemers (2012) [2] ). A graph is d-extremal (resp. d S L -extremal) if it has diameter d and exactly d + 1 distinct eigenvalues (resp. signless Laplacian eigenvalues), and a graph is split if its vertex set can be partitioned into a clique and a stable set. Such graphs have diameter at most three. If all vertex degrees in a split graph are either d ˜ or d ˆ , then we say it is ( d ˜ , d ˆ ) -bidegreed. In this paper, we present a complete classification of the connected bidegreed 3 S L -extremal split graphs using the association of split graphs with combinatorial designs.

The inverse degree of a graph was defined as the sum of the inverses of the degrees of the vertices. In this paper, we focus on finding sufficient conditions in terms of the inverse degree for a graph to be \(k\)-path-coverable, \(k\)-edge-hamiltonian, Hamilton-connected and traceable, respectively. The results obtained are not dropped.

An even factor of a graph G is a spanning subgraph in G such that the degree of each vertex is a positive even integer. In this paper, we show that for any induced claw of simple graph G of order at least 10, if there exists at least a pair of vertices out of the claw such that they are the common neighbors of nonadjacent vertices of the claw, then G has an even factor if and only if $$\delta (G)\ge 2$$ and every odd branch-bond of G contains a branch of length 1. The even factor of claw-heavy graphs was also characterized.

Fault tolerance is especially important for interconnection networks, since the growing size of networks increases their vulnerability to component failures. A classical measure for the fault tolerance of a network in the case of vertex failures is its connectivity. The connectivity κ (G) of a connected graph G is the least positive integer κ such that there is S ⊂ V, |S| = κ and G–S is disconnected or reduces to the trivial graph K1. The edge connectivity λ(G) of G is similarly defined. It is well known that κ (G) ≤ λ (G) ≤ δ (G). A graph G is called maximally (edge) connected if κ (G) = δ (G)( λ (G) = δ (G)), max-κ (max-λ) for simply. A connected graph G = (V, E) is called supper- κ (resp. super-λ) if every minimum vertex cut (edge cut) of G is the set of neighbors of some vertex in G. We introduce a new kind of network called k-split network. A network based on a graph G = (X1 U X2 U … ⊂ Xk, I, E) is called a k-split network, if its vertex set V can be partitioned into κ + 1 stable sets I, X1, X2, …, Xκ such that X1 U X2 U … U Xκ induces a complete k-partite graph and an independent set I. In this note, we show that: G = (X1UX2 … UXκ, I, E) is a non-complete connected κ-split graph with κ ≥ 3 and |X1| ≤ |X2| ≤ … ≤ |Xκ|. Then we have (1) If |X1 U X2 … U Xκ–1| ≥ δ(G), then κ (G) = δ (G). (2) If |X1 U X2 … U Xκ–1|δ, then G is super-κ. (5) G is super-λ.

Let G = (V (G),E(G)) be a graph. Gould and Hynds (1999) showed a well-known characterization of G by its line graph L(G) that has a 2-factor. In this paper, by defining two operations, we present a characterization for a graph G to have a 2-factor in its line graph L(G). A graph G is called N 2-locally connected if for every vertex x ∈ V (G), G[{y ∈ V (G); 1 ⩽ dist G (x, y) ⩽ 2}] is connected. By applying the new characterization, we prove that every claw-free graph in which every edge lies on a cycle of length at most five and in which every vertex of degree two that lies on a triangle has two N 2-locally connected adjacent neighbors, has a 2-factor. This result generalizes the previous results in papers: Li, Liu (1995) and Tian, Xiong, Niu (2012), and is the best possible.

The k-th power of a graph G, denoted by Gk, is a graph with the same set of vertices as G, such that two vertices are adjacent in Gk if and only if their distance in G is at most k. The Harary index H is the sum of the reciprocal distances of all pairs of vertices of the underlying graph. Lower and upper bounds on H(Gk) are obtained. A Nordhaus-Gaddum type inequality for H(Gk) is also established.

The authors Milicevic et al. introduced the reformulated Zagreb indices [1], which is a generalization of classical Zagreb indices of chemical graph theory. In this paper, we mainly consider the maximum and minimum for the first reformulated index of graphs with connectivity at most k. The corresponding extremal graphs are characterized.