Search

Completely independent spanning trees in a graph G are spanning trees of G such that for any two distinct vertices of G, the paths between them in the spanning trees are pairwise edge-disjoint and internally vertex-disjoint. In this paper, we present a tight lower bound on the maximum number of completely independent spanning trees in L(G), where L(G) denotes the line graph of a graph G. Based on a new characterization of a graph with k completely independent spanning trees, we also show that for any complete graph K n of order n ≥ 4 , there are ⌊ n + 1 2 ⌋ completely independent spanning trees in L (K n) where the number ⌊ n + 1 2 ⌋ is optimal, such that ⌊ n + 1 2 ⌋ completely independent spanning trees still exist in the graph obtained from L (K n) by deleting any vertex (respectively, any induced path of order at most n 2 ) for n = 4 or odd n ≥ 5 (respectively, even n ≥ 6 ). Concerning the connectivity and the number of completely independent spanning trees, we moreover show the following, where δ (G) denotes the minimum degree of G. Every 2k-connected line graph L(G) has k completely independent spanning trees if G is not super edge-connected or δ (G) ≥ 2 k . Every (4 k - 2) -connected line graph L(G) has k completely independent spanning trees if G is regular. Every (k 2 + 2 k - 1) -connected line graph L(G) with δ (G) ≥ k + 1 has k completely independent spanning trees. [ABSTRACT FROM AUTHOR]

Let F t (n) denote the family of all connected graphs of order n with clique number t. In this paper, we present a new upper bound for the chromatic polynomial of a graph G in F t (n) in terms of the clique number of G. Moreover, we also show that the conjecture proposed by Tomescu, which says that if x ≥ k ≥ 4 and G is a connected graph on n vertices with chromatic number k, then P (G , x) ≤ (x) k (x - 1) n - k holds under certain conditions, where (x) k = x (x - 1) ⋯ (x - k + 1) , such as the clique number ω (G) = k ≥ 4 , ω (G) = k - 1 (k ≥ 7) with two (k - 1) -cliques having at most k - 3 vertices in common, or maximum degree ▵ (G) = n - 2 . [ABSTRACT FROM AUTHOR]

The concept of antimagic labelings of a graph is to produce distinct vertex sums by labeling edges through consecutive numbers starting from one. A long-standing conjecture is that every connected graph, except a single edge, is antimagic. Some graphs are known to be antimagic, but little has been known about sparse graphs, not even trees. This paper studies a weak version called k-shifted-antimagic labelings which allow the consecutive numbers starting from k + 1 , instead of starting from 1, where k can be any integer. This paper establishes connections among various concepts proposed in the literature of antimagic labelings and extends previous results in three aspects: Some classes of graphs, including trees and graphs whose vertices are of odd degrees, which have not been verified to be antimagic are shown to be k-shifted-antimagic for sufficiently large k. Some graphs are proved k-shifted-antimagic for all k, while some are proved not for some particular k. Disconnected graphs are also considered. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with order n and adjacency matrix A (G) . The characteristic polynomial of G is defined by ϕ (G ; λ) = det (λ I - A (G)) = ∑ i = 0 n a i (G) λ n - i , where a i (G) is called the i-th adjacency coefficient of G. Denote by B n , m the collection of all connected bipartite graphs having n vertices and m edges. A bipartite graph G is referred as 4-Sachs optimal if a 4 (G) = min { a 4 (H) ∣ H ∈ B n , m }. For any given integer pair (n, m), in this paper we investigate the 4-Sachs optimal bipartite graphs. Firstly, we show that each 4-Sachs optimal bipartite graph is a difference graph. Then we deduce some structural properties on 4-Sachs optimal bipartite graphs. Especially, we determine the unique 4-Sachs optimal bipartite (n, m)-graphs for n ≥ 5 and n - 1 ≤ m ≤ 2 (n - 2) . Finally, we provide a method to construct a class of cospectral difference graphs, which disprove a conjecture posed by Andelić et al. (J Czech Math 70:1125–1138, 2020). [ABSTRACT FROM AUTHOR]

Let G be a graph, a dominating induced matching (DIM) of G is an induced matching that dominates every edge of G. In this paper we show that if a graph G has a DIM, then χ (G) ≤ 3 . Also, it is shown that if G is a connected graph whose all edges can be partitioned into DIM, then G is either a regular graph or a biregular graph and indeed we characterize all graphs whose edge set can be partitioned into DIM. Also, we prove that if G is an r-regular graph of order n whose edges can be partitioned into DIM, then n is divisible by 2 r - 1 r - 1 and n = 2 r - 1 r - 1 if and only if G is the Kneser graph with parameters r - 1 , 2 r - 1 . [ABSTRACT FROM AUTHOR]

A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number is the minimum cardinality of a paired-dominating set of G. The paired-domination subdivision number is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the paired-domination number. It was conjectured that the paired-domination subdivision number is at most n - 1 for every connected graph G of order n ≥ 3 which does not contain isolated vertices. In this paper, we settle the conjecture in the affirmative. [ABSTRACT FROM AUTHOR]

Given two graphs G and H, the k-colored Gallai–Ramsey number g r k (G : H) is defined to be the minimum integer n such that every k-coloring of the complete graph on n vertices contains either a rainbow copy of G or a monochromatic copy of H. In this paper, we consider g r k (K 3 : H) , where H is a connected graph with five vertices and at most six edges. There are in total thirteen graphs in this graph class, and the Gallai–Ramsey numbers for eight of them have been studied step by step in several papers. We determine all the Gallai–Ramsey numbers for the remaining five graphs, and we also obtain some related results for a class of unicyclic graphs. As applications, we find the mixed Ramsey spectra S (n ; H , K 3) for these graphs by using the Gallai–Ramsey numbers. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph, and D(G) be the distance matrix of G. Suppose that D max (G) and λ 1 (G) are the maximum row sum and the spectral radius of D(G), respectively. In this paper, we give a lower bound for D max (G) - λ 1 (G) , and characterize the extremal graphs attaining the bound. As a corollary, we solve a conjecture posed by Liu, Shu and Xue. [ABSTRACT FROM AUTHOR]

Given a connected graph G = (V (G) , E (G)) , the length of a shortest path from a vertex u to a vertex v is denoted by d(u, v). For a proper subset W of V(G), let m(W) be the maximum value of d(u, v) as u ranging over W and v ranging over V (G) \ W . The proper subset W = { w 1 , ... , w | W | } is a completeness-resolving set of G if Ψ W : V (G) \ W ⟶ [ m (W) ] | W | , u ⟼ (d (w 1 , u) , ... , d (w | W | , u)) is a bijection, where [ m (W) ] | W | = { (a (1) , ... , a (| W |)) ∣ 1 ≤ a (i) ≤ m (W) for each i = 1 , ... , | W | }. A graph is completeness-resolvable if it admits a completeness-resolving set. In this paper, we first construct the set of all completeness-resolvable graphs by using the edge coverings of some vertices in given bipartite graphs, and then establish posets on some subsets of this set by the spanning subgraph relationship. Based on each poset, we find the maximum graph and give the lower and upper bounds for the number of edges in a minimal graph. Furthermore, minimal graphs satisfying the lower or upper bound are characterized. [ABSTRACT FROM AUTHOR]

A double Roman dominating function (DRDF) on a graph G = (V , E) is a function f : V → { 0 , 1 , 2 , 3 } having the property that if f (v) = 0 , then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f (w) = 3 , and if f (v) = 1 , then vertex v must have at least one neighbor w with f (w) ≥ 2 . The weight of a DRDF is the sum of its function values over all vertices, and the double Roman domination number γ dR (G) is the minimum weight of a DRDF on G. Recently, Khoeilar et al. (Discrete Appl Math 270:159–167, 2019) proved that a connected graph G of order n with minimum degree two different from C 5 and C 7 , satisfies γ dR (G) ≤ 11 10 n. In this paper, we show that this upper bound can be improved to 20 19 n if G is restricted to connected graphs of order n with minimum degree at least two and no C 5 -cycle such that G ∉ { C 7 , C 11 , C 13 , C 17 }. Moreover, we provide an infinite family of graphs attaining this bound. [ABSTRACT FROM AUTHOR]

Let G be a graph and P be a property of graphs. A subset S ⊆ V (G) is called a P -admissible set of G if G - N [ S ] admits the property P . The P -admission number of G, denoted by η (G , P) , is the cardinality of a minimum P -admissible set in G. For a positive integer k, we say a graph G has the property R k if the radius of each component of G is at most k. In particular, η (G , R 1) is the cardinality of a smallest set S such that each component of G - N [ S ] has a universal vertex. In this paper, we establish sharp upper bound for η (G , R 1) for a connected graph G. We show that for a connected graph G ≠ C 7 of order n, η (G , R 1) ≤ n 4 . The bound is sharp. Several related problems are proposed. [ABSTRACT FROM AUTHOR]

Zero forcing (zero forcing number, denoted by F(G)) of a connected graph G, which proposed by the AIM-minimum rank group in 2008, has been received much attention. In 2015, Davila introduced total forcing which is as a strengthening form of zero forcing. The total forcing number of G is the minimum cardinality of a total forcing set in G, denoted by F t (G) . It is easy to deduce that for any graph G, F (G) ≤ F t (G) ≤ 2 F (G) . In addition, we know that F t (T) ≥ F (T) + 1 for a tree T. Our interest is to study the structure of the tree T with F t (T) = 2 F (T) . In the paper, we characterize all trees meets the condition. In fact, these trees can be reconstructed by beginning with a path through repeating a tree operation. [ABSTRACT FROM AUTHOR]

A connected graph G has property E(m, n) (or more briefly "G is E(m, n)") if for every pair of disjoint matchings M and N in G with | M | = m and | N | = n respectively, there is a perfect matching F in G such that M ⊆ F and N ∩ F = ∅ . In particular, a graph which has the E(m, 0) property is said to be m-extendable. Also a graph G which has the property that G - u - v has a perfect matching for every pair of distinct vertices u and v is said to be bicritical. In the present paper we investigate further the interrelation between extendability and criticality. In Lovász and Plummer (Matching theory, North-Holland Publisher, Amsterdam, 1986) author proved that a 2-extendable graph is either 1-extendable and bipartite, or else bicritical (clearly a graph cannot be both). In the present paper we generalize this result by extending the notion of bicriticality in several ways and studying the relationships of these extensions to extendability. [ABSTRACT FROM AUTHOR]

Let G be a simple undirected graph, I the identity matrix, and A(G) an adjacency matrix of G. Then the permanental sum of G equals to the permanent of the matrix I + A (G) . Since the computation of the permanental sum of a graph is #P-complete, it is desirable to have good bounds. In this paper, we affirm a sharp upper bound for general graphs conjectured by Wu and So. Moreover, we prove a sharp lower bound for connected tricyclic graphs. Lastly, several unsolved problems about permanental sum are presented. [ABSTRACT FROM AUTHOR]

Let H G (x , y) be the expected hitting time from vertex x to vertex y for the first time on a simple connected graph G and φ (G) : = max H G (x , y) : x , y ∈ V (G) be called the hitting time of G. In this paper, sharp upper and lower bounds for φ (G) among all n-vertex bicyclic graphs are presented and the extremal graphs are determined. [ABSTRACT FROM AUTHOR]

An edge-colored graph is called rainbow (or heterochromatic) if all its edges have distinct colors. It is known that if an edge-colored connected graph H has minimum color degree at least |H|/2 and has a certain property, then H has a rainbow spanning tree. In this paper, we prove that if an edge-colored connected bipartite graph G has minimum color degree at least |G|/3 and has a certain property, then G has a rainbow spanning tree. We also give a similar sufficient condition for G to have a properly colored spanning tree. Moreover, we show that these minimum color-degree conditions are sharp. [ABSTRACT FROM AUTHOR]

A set S of vertices is a determining set of a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G, denoted by Det (G) , is the smallest size of a determining set. In this paper, we give an explicit characterization for connected graphs of order n with determining number n - 3 [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]

The relation between Hamiltonicity and toughness of a graph is a long standing research problem. The paper studies the Hamiltonicity of the Cartesian product graph G 1 □ G 2 of graphs G 1 and G 2 satisfying that G 1 is traceable and G 2 is connected with a path factor. Let P n be the path of order n and H be a connected bipartite graph. With certain requirements of n, we show that the following three statements are equivalent: (i) P n □ H is Hamiltonian; (ii) P n □ H is 1-tough; and (iii) H has a path factor. [ABSTRACT FROM AUTHOR]

Let α ≥ 0 and k ≥ 2 be integers. For a graph G, the total k-excess of G is defined as te (G ; k) = ∑ v ∈ V (G) max { d G (v) - k , 0 } . In this paper, we propose a new closure concept for a spanning tree with bounded total k-excess. We prove that: Let G be a connected graph, and let u and v be two non-adjacent vertices of G. If G satisfies one of the following conditions, then G has a spanning tree T such that te (T ; k) ≤ α if and only if G + u v has a spanning tree T ′ such that te (T ′ ; k) ≤ α : max { ∑ x ∈ X d G (x) : X is a subset of S with | X | = k } ≥ | G | - 1 for every independent set S in G of order k + 1 such that { u , v } ⊆ S ; or max { ∑ x ∈ X d G (x) : X is a subset of S with | X | = k } ≥ | G | - α - 1 for every independent set S in G of order k + α + 1 such that S ∩ { u , v } ≠ ∅. We also show examples to show that these conditions are sharp. [ABSTRACT FROM AUTHOR]

The connected graph of degree sequence 3, 3, 3, 1, 1, 1 is called a net, and the vertices of degree 1 in a net are called its endvertices. Broersma conjectured in 1993 that a 2-connected graph G with no induced K 1 , 3 is hamiltonian if every endvertex of each induced net of G has degree at least (| V (G) | - 2) / 3 . In this paper we prove this conjecture in the affirmative. [ABSTRACT FROM AUTHOR]

For given graphs G1,G2,...,Gk,k≥2, the multicolor Ramsey numberR(G1,G2,...,Gk) is the smallest integer n such that if we arbitrarily color the edges of the complete graph of order n with k colors, then it contains a monochromatic copy of Gi in color i, for some 1≤i≤k. The main result of the paper is a theorem which establishes the connection between the multicolor Ramsey number and the appropriate multicolor bipartite Ramsey number together with the ordinary Ramsey number. The remaining part of the paper consists of a number of corollaries which are derived from the main result and from known results for Ramsey numbers and bipartite Ramsey numbers. We provide some new exact values or generalize known results for multicolor Ramsey numbers of paths, cycles, stripes and stars versus other graphs. [ABSTRACT FROM AUTHOR]

Let T be a tree with m edges. It was conjectured that every m-regular bipartite graph can be decomposed into edge-disjoint copies of T. In this paper, we prove that every 6-regular bipartite graph can be decomposed into edge-disjoint paths with 6 edges. As a consequence, every 6-regular bipartite graph on n vertices can be decomposed into n 2 paths, which is related to the well-known Gallai's Conjecture: every connected graph on n vertices can be decomposed into at most n + 1 2 paths. [ABSTRACT FROM AUTHOR]

A proper edge coloring of a graph G is strict neighbor-distinguishing if for any two adjacent vertices u and v, the set of colors used on the edges incident to u and the set of colors used on the edges incident to v are not included with each other. The strict neighbor-distinguishing index of G is the minimum number χ snd ′ (G) of colors in a strict neighbor-distinguishing edge coloring of G. In this paper, we prove that every connected subcubic graph G with δ (G) ≥ 2 has χ snd ′ (G) ≤ 7 , and moreover χ snd ′ (G) = 7 if and only if G is a graph obtained from the graph K 2 , 3 by inserting a 2-vertex into one edge. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a finite connected graph along with a coloring of the vertices of G using the colors in a given set X. In this paper, we introduce multi-color forcing, a generalization of zero-forcing on graphs, and give conditions in which the multi-color forcing process terminates regardless of the number of colors used. We give an upper bound on the number of steps required to terminate a forcing procedure in terms of the number of vertices in the graph on which the procedure is being applied. We then focus on multi-color forcing with three colors and analyze the end states of certain families of graphs, including complete graphs, complete bipartite graphs, and paths, based on various initial colorings. We end with a few directions for future research. [ABSTRACT FROM AUTHOR]

An edge labeling of a connected graph G = (V , E) is said to be local antimagic if it is a bijection f : E → { 1 , ... , | E | } such that for any pair of adjacent vertices x and y, f + (x) ≠ f + (y) , where the induced vertex label f + (x) = ∑ f (e) , with e ranging over all the edges incident to x. The local antimagic chromatic number of G, denoted by χ la (G) , is the minimum number of distinct induced vertex labels over all local antimagic labelings of G. In this paper, we give counterexamples to the lower bound of χ la (G ∨ O 2) that was obtained in [Local antimagic vertex coloring of a graph, Graphs Combin. 33:275–285 (2017)]. A sharp lower bound of χ la (G ∨ O n) and sufficient conditions for the given lower bound to be attained are obtained. Moreover, we settled Theorem 2.15 and solved Problem 3.3 in the affirmative. We also completely determined the local antimagic chromatic number of complete bipartite graphs. [ABSTRACT FROM AUTHOR]

A mixed graph is a graph with undirected and directed edges. Guo and Mohar in 2017 determined all mixed graphs whose Hermitian spectral radii are less than 2. In this paper, we give a sufficient condition which can make Hermitian spectral radius of a connected mixed graph strictly decreasing when an edge or a vertex is deleted, and characterize all mixed graphs with Hermitian spectral radii at most 2 and with no cycle of length 4 in their underlying graphs. [ABSTRACT FROM AUTHOR]

Let G be a graph, ν the order of G and k a positive integer such that k ≤ (ν - 2) / 2 . Then G is said to be k-extendable if it has a matching of size k and every matching of size k extends to a perfect matching of G. A graph G is Hamiltonian if it contains a Hamiltonian cycle. A graph G is Hamiltonian-connected if, for any two of its vertices, it contains a spanning path joining the two vertices. In this paper, we discuss k-extendable nonbipartite graphs with κ (G) ≥ 2 k + r where k ≥ 1 and r ≥ 0 . It is shown that if ν ≤ 6 k + 2 r , then G is Hamiltonian; and if ν > 6 k + 2 r , then G has a longest cycle C such that | V (C) | ≥ 6 k + 2 r ; and if ν < 6 k + 2 r , then G is Hamiltonian-connected; and if ν ≥ 6 k + 2 r , then for each pair of vertices z 1 and z 2 of G, there is a path P of G joining z 1 and z 2 such that | V (P) | ≥ 6 k + 2 r - 2 . All the bounds are sharp and all results can be extended to 2k-factor-critical graphs. [ABSTRACT FROM AUTHOR]

This paper deals with various extremal problems involving two important parameters associated to a connected graph, say G. The first parameter is the largest complementarity eigenvalue: it is denoted by ϱ (G) and it is simply the spectral radius or index of the graph. Next in importance comes the second largest complementarity eigenvalue: it is denoted by ϱ 2 (G) and it is equal to the largest spectral radius among the children of G. By definition, a child or vertex-deleted connected subgraph of G is an induced subgraph obtained by removing a noncut vertex from G. In the first part of this work, we address the problem of identifying the eldest children and the youngest parents of G. We also analyze the uniqueness of such children and parents. An eldest child of G is a child whose spectral radius attains the value ϱ 2 (G) . The concept of youngest parent is somewhat dual to that of eldest child. The second part of this work is about minimization and maximization of the functions ϱ 2 and ϱ - ϱ 2 on special classes of connected graphs. We establish several new results and propose a number of conjectures. [ABSTRACT FROM AUTHOR]

Let G be a graph on even number of vertices. A perfect matching of G is a set of independent edges which cover each vertex of G. For an integer t ≥ 1 , G is t-extendable if G has a perfect matching, and for any t independent edges, G has a perfect matching which contains these given t edges. The graph G is bi-critical if for any two vertices u and v, the graph G - u , v contains a perfect matching. Let G be a connected k-regular graph. In this paper, we obtain two sharp sufficient eigenvalue conditions for a connected k-regular graph to be 1-extendable and bi-critical, respectively. Our results are in term of the second largest eigenvalue of the adjacency matrix of G. We also give examples that show that there is no good spectral characterization (in term of the second largest eigenvalue of the adjacency matrix) for 2-extendability of regular graphs in general. Also, for any integer 1 ≤ ℓ < k + 2 2 , we obtain an eigenvalue condition for G to be (ℓ + 1) -connected. [ABSTRACT FROM AUTHOR]

It has been conjecture that every finite connected Cayley graph contains a hamiltonian cycle. Given a finite group G and a connection set S, the Cayley graph Cay(G, S) will be called normal if for every g ∈ G we have that g - 1 S g = S . In this paper we present some conditions on the order of the elements of the connexion set which imply the existence of a hamiltonian cycle in the graph and we construct it in an explicit way. [ABSTRACT FROM AUTHOR]

For two graphs A and B, a graph G is called { A , B } -free if G contains neither A nor B as an induced subgraph. Let P n denote the path of order n. For nonnegative integers k, ℓ and m, let N k , ℓ , m be the graph obtained from K 3 and three vertex-disjoint paths P k + 1 , P ℓ + 1 , P m + 1 by identifying each of the vertices of K 3 with one endvertex of one of the paths. Let Z k = N k , 0 , 0 and B k , ℓ = N k , ℓ , 0 . Bedrossian characterized all pairs { A , B } of connected graphs such that every 2-connected { A , B } -free graph is Hamiltonian. All pairs appearing in the characterization involve the claw ( K 1 , 3 ) and one of N 1 , 1 , 1 , P 6 and B 1 , 2 . In this paper, we characterize connected graphs that are (i) { K 1 , 3 , Z 2 } -free but not B 1 , 1 -free, (ii) { K 1 , 3 , B 1 , 1 } -free but not P 5 -free, or (iii) { K 1 , 3 , B 1 , 2 } -free but not P 6 -free. The third result is closely related to Bedrossian's characterization. Furthermore, we apply our characterizations to some forbidden pair problems. [ABSTRACT FROM AUTHOR]

Koolen et al. showed that if a connected graph with smallest eigenvalue at least - 3 has large minimal valency, then it is 2-integrable. In this paper, we will prove that a lower bound for the minimal valency is 166. [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n with vertex set V(G). For positive integers a and b, a subset S ⊆ V (G) is an (a, b)-dominating set if every vertex v ∈ S is adjacent to at least a vertices inside S and every vertex v ∈ V \ S is adjacent to at least b vertices inside S. The minimum cardinality of an (a, b)-dominating set for G is called the (a, b)-domination number of G and is denoted by γ a , b (G) . There are various results on upper bounds for γ a , b (G) when G is a regular graph or a and b are small numbers. In the first part of this paper, for a given graph G with the minimum degree of at least max { a , b } , we define a new graph G ′ associated to G and show that the independence number of this graph is related to γ a , b (G) . In the next part, using Lovász local lemma, we give a randomized approach to improve previous results on the upper bounds for γ a , b (G) in some special cases. [ABSTRACT FROM AUTHOR]

In this paper, we show the following: Let G be a connected claw-free graph such that G has a connected induced subgraph H that has a pair of vertices { v 1 , v 2 } of degree one in H whose distance is d + 2 in H. Then H has an induced subgraph F, which is isomorphic to B i , j , with { v 1 , v 2 } ⊆ V (F) and i + j = d + 1 , with a well-defined exception. Here B i , j denotes the graph obtained by attaching two vertex-disjoint paths of lengths i , j ≥ 1 to a triangle. We also use the result above to strengthen the results in Xiong et al. (Discrete Math 313:784–795, 2013) in two cases, when i + j ≤ 9 , and when the graph is Γ 0 -free. Here Γ 0 is the simple graph with degree sequence 4, 2, 2, 2, 2. Let i , j > 0 be integers such that i + j ≤ 9 . Then every 3-connected { K 1 , 3 , B i , j } -free graph G is hamiltonian, and every 3-connected { K 1 , 3 , Γ 0 , B 2 i , 2 j } -free graph G is hamiltonian. The two results above are all sharp in the sense that the condition " i + j ≤ 9 " couldn't be replaced by ' ' i + j ≤ 10 ". [ABSTRACT FROM AUTHOR]

A connected graph G with at least 2 k + 2 vertices is called k-extendable if it has a matching of size k and every such matching can extend to a perfect matching in G. A graph G is an (n, k)-graph if for any set S of n vertices, the subgraph G - S is k-extendable. For a surface Σ , Lu and Wang established the pleasurable formula of the minimum number k = μ (n , Σ) such that no Σ -embeddable graph is an (n, k)-graph by fixing the parameter n. In this paper, we make the other parameter k fixed and figure out the minimum number n = ρ (k , Σ) such that no Σ -embeddable graph is an (n, k)-graph. By the way, the well-known Dean's formula (Theorem 1.1) can be reproduced. Further, we find out an upper bound on the order of (n, k)-graphs embedded in Σ for any non-negative integers n, k with k ≥ 1 , n + 2 k ≥ 6 and (n , k) ≠ (0 , 3) , which yields two results: (i) there are infinitely many (n, k)-graphs embedded in the sphere (resp. the projective plane) if and only if n + 2 k ≤ 4 ; (ii) for each surface Σ homeomorphic to neither the sphere nor the projective plane, there are infinitely many Σ -embeddable (n, k)-graphs if and only if n + 2 k ≤ 5 or (n , k) = (0 , 3) . [ABSTRACT FROM AUTHOR]

A threshold graph G of order n is defined by binary sequence of length n. In this paper, we consider the adjacent matrix of a connected threshold graph, and give the eigenvalues distribution in threshold graphs. Moreover, we pick out all the threshold graphs with distinct eigenvalues, and determine the HOMO–LUMO index of threshold graphs. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. An edge cut set M of G is a cyclic edge cut set if there are at least two components of G - M which contain a cycle. The cyclic edge-connectivity of G is the minimum cardinality of a cyclic edge cut set (if exists) of G. In this paper, we show that the cyclic edge-connectivity of a connected strongly regular graph G (not K 3 , 3 ) of degree k ≥ 3 with girth c is equal to (k - 2) c , where c = 3 , 4 or 5. Moreover, if G is not the triangular graph srg-(10, 6, 3, 4), the complete multi-partite graph K 2 , 2 , 2 , 2 or the lattice graph srg-(16, 6, 2, 2), then each cyclic edge cut set of size (k - 2) c is precisely the set of edges incident with a cycle of length c in G. [ABSTRACT FROM AUTHOR]

A total dominating set of a graph G is a dominating set S of G such that the subgraph induced by S contains no isolated vertex, where a dominating set of G is a set of vertices of G such that each vertex in V (G) \ S has a neighbor in S. A (total) dominating set S is said to be minimal if S \ { v } is not a (total) dominating set for every v ∈ S . The upper total domination number Γ t (G) and the upper domination number Γ (G) are the maximum cardinalities of a minimal total dominating set and a minimal dominating set of G, respectively. For every graph G without isolated vertices, it is known that Γ t (G) ≤ 2 Γ (G) . The case in which Γ t (G) Γ (G) = 2 has been studied in Cyman et al. (Graphs Comb 34:261–276, 2018), which focused on the characterization of the connected cubic graphs and proposed one problem to be solved and two questions to be answered in terms of the value of Γ t (G) Γ (G) . In this paper, we solve this problem, i.e., the characterization of the subcubic graphs G that satisfy Γ t (G) Γ (G) = 2 , by constructing a class of subcubic graphs, which we call triangle-trees. Moreover, we show that the answers to the two questions are negative by constructing connected cubic graphs G that satisfy Γ t (G) Γ (G) > 3 2 and a class of regular non-complete graphs G that satisfy Γ t (G) Γ (G) = 2 . [ABSTRACT FROM AUTHOR]

Let H be a set of connected graphs. A graph is said to be H-free if it does not contain any member of H as an induced subgraph. In this paper, we characterize all pairs R, S such that every connected {R,S}-free graph has the same (vertex)-connectivity and edge-connectivity. [ABSTRACT FROM AUTHOR]

A graph G is said to be pancyclic if G contains cycles of lengths from 3 to |V(G)|. For a positive integer i, we use Zi to denote the graph obtained by identifying an endpoint of the path Pi+1 with a vertex of a triangle. In this paper, we show that every 4-connected claw-free Z8-free graph is either pancyclic or is the line graph of the Petersen graph. This implies that every 4-connected claw-free Z6-free graph is pancyclic, and every 5-connected claw-free Z8-free graph is pancyclic. [ABSTRACT FROM AUTHOR]

In this paper we consider one of the most extensively studied graph search parameters, namely the zero-forcing number of a graph. We relate the zero-forcing number to the brushing number, which as a graph parameter gained recent attention due to certain industrial applications where a network system needs to be cleaned efficiently. In particular, we prove that the zero-forcing number of the line graph is an upper bound for the brushing number by constructing a brush configuration based on a zero-forcing set for the line graph. Eroh, Kang and Yi conjectured that the zero-forcing number of a graph is no more than the zero-forcing number of its line graph, which we settle in the affirmative. Moreover we prove that the brushing number of a graph is no more than the brushing number of its line graph. All three bounds are shown to be tight. [ABSTRACT FROM AUTHOR]

Two graphs are adjacency cospectral (respectively, permanental cospectral) if they have the same adjacency spectrum (respectively, permanental spectrum). In this paper, we present a new method to construct new adjacency cospectral and permanental cospetral pairs of graphs from smaller ones. As an application, we obtain an infinite family of pairs of Cartesian product graphs which are adjacency cospectral and permanental cospetral. [ABSTRACT FROM AUTHOR]

An octad triple is a set of three octads, octads being the blocks of the S(5, 8, 24) Steiner system. In this paper we determine the orbits of M24, the largest Mathieu group, upon the set of octad triples. [ABSTRACT FROM AUTHOR]

In this paper, we study (zero) forcing sets which induce connected subgraphs of a graph. The minimum cardinality of such a set is called the connected forcing number of the graph. We provide sharp upper and lower bounds on the connected forcing number in terms of the minimum degree, maximum degree, girth, and order of the graph. [ABSTRACT FROM AUTHOR]

An edge-colored graph G is conflict-free connected if every 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 the smallest number of colors needed in order to make G conflict-free connected. For a graph G,  let C(G) be the subgraph of G induced by its set of cut-edges. In this paper, we first show that, if G is a connected non-complete graph G of order n≥9 with C(G) being a linear forest and with the minimum degree δ(G)≥max{3,n-45}, then cfc(G)=2. The bound on the minimum degree is best possible. Next, we prove that, if G is a connected non-complete graph of order n≥33 with C(G) being a linear forest and with d(x)+d(y)≥2n-95 for each pair of two nonadjacent vertices x, y of V(G), then cfc(G)=2. Both bounds, on the order n and the degree sum, are tight. Moreover, we prove several results concerning relations between degree conditions on G and the number of cut edges in G. [ABSTRACT FROM AUTHOR]

A graph is called H-free if it has no induced subgraph isomorphic to H. A graph is called Ni-locally connected if G[{x∈V(G):1≤dG(w,x)≤i}] is connected and N2-locally connected if G[{uv:{uw,vw}⊆E(G)}] is connected for every vertex w of G, respectively. In this paper, we prove the following.Every 2-connected P7-free graph of minimum degree at least three other than the Petersen graph has a spanning Eulerian subgraph. This implies that every H-free 3-connected graph (or connected N4-locally connected graph of minimum degree at least three) other than the Petersen graph is supereulerian if and only if H is an induced subgraph of P7, where Pi is a path of i vertices.Every 2-edge-connected H-free graph other than {K2,2k+1:kis a positive integer} is supereulerian if and only if H is an induced subgraph of P4.If every connected H-free N3-locally connected graph other than the Petersen graph of minimum degree at least three is supereulerian, then H is an induced subgraph of P7 or T2,2,3, i.e., the graph obtained by identifying exactly one end vertex of P3,P3,P4, respectively.If every 3-connected H-free N2-locally connected graph is hamiltonian, then H is an induced subgraph of K1,4. We present an algorithm to find a collapsible subgraph of a graph with girth 4 whose idea is used to prove our first conclusion above. Finally, we propose that the reverse of the last two items would be true. [ABSTRACT FROM AUTHOR]

A bipartition of the vertex set of a graph is called balanced if the sizes of the sets in the bipartition differ by at most one. Bolloba´s and Scott proved that every regular graph with m edges admits a balanced bipartition V1, V2 of V(G) such that max{e(V1),e(V2)}

In 1970, Plummer defined a well-covered graph to be a graph G in which all maximal independent sets are in fact maximum. Later Hartnell and Rall showed that if the Cartesian product G□H is well-covered, then at least one of G or H is well-covered. In this paper, we consider the problem of classifying all well-covered Cartesian products. In particular, we show that if the Cartesian product of two nontrivial, connected graphs of girth at least 4 is well-covered, then at least one of the graphs is K2. Moreover, we show that K2□K2 and C5□K2 are the only well-covered Cartesian products of nontrivial, connected graphs of girth at least 5. [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n and let k∈{1,…,n-1}. The k-token graph Fk(G) of G is the graph whose vertices are the k-subsets of V(G), where two vertices are adjacent in Fk(G) whenever their symmetric difference is an edge of G. In 2012 Fabila et al. conjectured that if G is t-connected and t≥k, then Fk(G) is k(t-k+1)-connected. In this paper we prove this conjecture. [ABSTRACT FROM AUTHOR]