Search

A graph is k-vertex-critical if χ (G) = k but χ (G - v) < k for all v ∈ V (G) . We construct new infinite families of k-vertex-critical (P 5 , C 5) -free graphs for all k ≥ 6 . Our construction generalises known constructions for 4-vertex-critical P 7 -free graphs and 5-vertex-critical P 5 -free graphs and is in contrast to the fact that there are only finitely many 5-vertex-critical (P 5 , C 5) -free graphs. In fact, our construction is even more well-structured, being (2 P 2 , K 3 + P 1 , C 5) -free. [ABSTRACT FROM AUTHOR]

We study diameter 2-critical graphs (for short, D2C graphs), i.e. graphs of diameter 2 whose diameter increases after removing any edge. Our results include structural considerations, new examples and a particular relationship with minimal 2-self-centered graphs stating that these graph classes are almost identical. We pay an attention to primitive D2C graphs (PD2C graphs) which, by definition, have no two vertices with the same set of neighbours. It is known that a graph of diameter 2 and order n, which has no dominating vertex, has at least 2n - 5 edges, and the graphs that attain this bound are also known. It occurs that exactly three of them are PD2C. The next natural step is to consider PD2C graphs with 2n - 4 edges. In this context, we determine an infinite family of PD2C graphs which, for every n ≥ 6, contains exactly one graph with 2n - 4 edges. We also prove that there are exactly seven Hamiltonian PD2C graphs with the required number of edges. We show that for n ≤ 13, there exists a unique PD2C graph with 2n - 4 edges that does not belong to the obtained family nor is Hamiltonian. It is conjectured that this is a unique example of such a graph. [ABSTRACT FROM AUTHOR]

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line Pn with n=|V(G)| vertices in such a way that the maximum number of overlapping edges (i.e., the congestion) is minimized. A graph G with a cutwidth of k is k-cutwidth critical if every proper subgraph of G has a cutwidth less than k and G is homeomorphically minimal. In this paper, we first verified some structural properties of k-cutwidth critical unicyclic graphs with k>1. We then mainly investigated the critical unicyclic graph set T with a cutwidth of four that contains fifty elements, and obtained a forbidden subgraph characterization of 3-cutwidth unicyclic graphs.

The cutwidth of a graph G is the smallest integer k ( k ≥ 1 ) such that the vertices of G are arranged in a linear layout [ v 1 , v 2 ,... , v n ] , in such a way that for each i = 1 , 2 ,... , n − 1 , there are at most k edges with one endpoint in { v 1 , v 2 ,... , v i } and the other in { v i + 1 ,... , v n } . The cutwidth problem for G is to determine the cutwidth k of G. A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has a cutwidth less than k and G is homeomorphically minimal. In this paper, except five irregular graphs, other 4-cutwidth critical graphs were resonably classified into two classes, which are graph class with a central vertex v 0 , and graph class with a central cycle C q of length q ≤ 6 , respectively, and any member of two graph classes can skillfuly achieve a subgraph decomposition S with cardinality 2, 3 or 4, where each member of S is either a 2-cutwith graph or a 3-cutwidth graph. [ABSTRACT FROM AUTHOR]

Let G1 and G2 be two undirected graphs. Let u1, v1 ∈ V (G1) and u2, v2 ∈ V (G2). A parallel composition forms a new graph H that combines G1 and G2 by contracting the vertices u1 with u2 and v1 with v2. A new kind of graph called a parallel critical graph is introduced in this paper. We present the critical property using the domination number of G1 and G2 and provide a necessary and sufficient condition for parallel critical graphs. Few results relating to some class of graphs and parallel composition are discussed in this paper. [ABSTRACT FROM AUTHOR]

Given a graph G, a coloring c : V (G) → {1, …, k} such that c(u) = c(v) = i implies that vertices u and v are at distance greater than i, is called a packing coloring of G. The minimum number of colors in a packing coloring of G is called the packing chromatic number of G, and is denoted by χρ(G). In this paper, we propose the study of χρ-critical graphs, which are the graphs G such that for any proper subgraph H of G, χρ(H) < χρ(G). We characterize χρ-critical graphs with diameter 2, and χρ-critical block graphs with diameter 3. Furthermore, we characterize χρ-critical graphs with small packing chromatic number, and we also consider χρ-critical trees. In addition, we prove that for any graph G and every edge e ∈ E(G), we have (χρ(G)+1)/2 ≤ χρ(G−e) ≤ χρ(G), and provide a corresponding realization result, which shows that χρ(G − e) can achieve any of the integers between these bounds.

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line P n with n = | V (G) | vertices in such a way that the maximum number of overlapping edges (i.e., the congestion) is minimized. A graph G with a cutwidth of k is k-cutwidth critical if every proper subgraph of G has a cutwidth less than k and G is homeomorphically minimal. In this paper, we first verified some structural properties of k-cutwidth critical unicyclic graphs with k > 1 . We then mainly investigated the critical unicyclic graph set T with a cutwidth of four that contains fifty elements, and obtained a forbidden subgraph characterization of 3-cutwidth unicyclic graphs. [ABSTRACT FROM AUTHOR]

The Gallai–Ramsey number g r k (K 3 : H 1 , H 2 , ⋯ , H k) is the smallest integer n such that every k-edge-colored K n contains either a rainbow K 3 or a monochromatic H i in color i for some i ∈ [ k ] . We define the star-critical Gallai–Ramsey number g r k ∗ (K 3 : H 1 , H 2 , ⋯ , H k) as the smallest integer s such that every k-edge-colored K n - K 1 , n - 1 - s contains either a rainbow K 3 or a monochromatic H i in color i for some i ∈ [ k ] . When H = H 1 = ⋯ = H k , we simply denote g r k ∗ (K 3 : H 1 , H 2 , ⋯ , H k) by g r k ∗ (K 3 : H) . We determine the star-critical Gallai–Ramsey numbers for complete graphs and some small graphs. Furthermore, we show that g r k ∗ (K 3 : H) is exponential in k if H is not bipartite, linear in k if H is bipartite but not a star and constant (not depending on k) if H is a star. [ABSTRACT FROM AUTHOR]

Let K1,k be a star of order k + 1 and Kn ⨆ K1,k the graph obtained from a complete graph Kn and an additional vertex v by joining v to k vertices of Kn. For graphs G and H, the star-critical Ramsey number r*(G, H) is the minimum integer k such that any red/blue edge-coloring of Kr−1 ⨆ K1,k contains a red copy of G or a blue copy of H, where r is the classical Ramsey number R(G, H). Let Cm denote a cycle of order m and Wn a wheel of order n + 1. Hook (2010) proved that r*(Wn, C3) = n + 3 for n ≥ 6. In this paper, we show that r*(Wn, Cm) = n + 3 for m odd, m ≥ 5 and n ≥ 3(m − 1)/2 + 2. [ABSTRACT FROM AUTHOR]

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line P n with n = | V (G) | vertices, in such a way that the maximum number of overlapping edges (i.e., the congestion) is minimized. A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal. In this paper, we mainly investigated a class of decomposable k-cutwidth critical graphs for k ≥ 2 , which can be decomposed into three (k - 1) -cutwidth critical subgraphs. [ABSTRACT FROM AUTHOR]

The cutwidth of a graph G is the smallest integer k (k≥1) such that the vertices of G are arranged in a linear layout [v1,v2,...,vn], in such a way that for each i=1,2,...,n−1, there are at most k edges with one endpoint in {v1,v2,...,vi} and the other in {vi+1,...,vn}. The cutwidth problem for G is to determine the cutwidth k of G. A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has a cutwidth less than k and G is homeomorphically minimal. In this paper, except five irregular graphs, other 4-cutwidth critical graphs were resonably classified into two classes, which are graph class with a central vertex v0, and graph class with a central cycle Cq of length q≤6, respectively, and any member of two graph classes can skillfuly achieve a subgraph decomposition S with cardinality 2, 3 or 4, where each member of S is either a 2-cutwith graph or a 3-cutwidth graph.

A dominating set D of a graph G = (V, E) is a nonsplit dominating set if the induced graph ⟨V −D⟩ is connected. The nonsplit domination number γns(G) is the minimum cardinality of a nonsplit domination set. The purpose of this paper is to initiate the investigation of those graphs which are critical in the following sense: A graph G is called vertex domination critical if γ(G−v) < γ(G) for every vertex v in G. A graph G is called vertex nonsplit critical if γns(G − v) < γns(G) for every vertex v in G. Initially we test whether some particular classes of graph are γns-critical or not and then we have shown that there is no existence of 2-γns-critical graph. Then 3-γns-critical graphs are characterized. [ABSTRACT FROM AUTHOR]

In this paper, we study multi-level distance edge labeling for infinite rectangular, hexagonal and triangular grids. We label the edges with non-negative integers. If the edges are adjacent, then their color difference is at least 2 and if they are separated by exactly a single edge, then their colors must be distinct. We find the edge coloring number of these grids to be 9, 7 and 16, respectively so that we could color the edges of a rectangular, hexagonal and triangular grid with at most 10, 8 and 17 colors, respectively using this coloring technique. Repeating the sequence pattern for different grids, we can color the edges of a grid of larger size.