Browse

1 - 10 of 6,145 items :

  • Mathematics x
Clear All

Abstract

A graph G is called r-spanning cyclable if for every r distinct vertices v 1, v 2, . . . , v r of G, there exists r cycles C 1, C 2, . . . , C r in G such that v i is on C i for every i, and every vertex of G is on exactly one cycle C i. In this paper, we consider the 2-spanning cyclable problem for the generalized Petersen graph GP (n, k). We solved the problem for k ≤ 4. In addition, we provide an additional observation for general k as well as stating a conjecture.

Abstract

An additive coloring of a graph G is a labeling of the vertices of G from {1, 2, . . . , k} such that two adjacent vertices have distinct sums of labels on their neighbors. The least integer k for which a graph G has an additive coloring is called the additive coloring number of G, denoted χ Σ (G). Additive coloring is also studied under the names lucky labeling and open distinguishing. In this paper, we improve the current bounds on the additive coloring number for particular classes of graphs by proving results for a list version of additive coloring. We apply the discharging method and the Combinatorial Nullstellensatz to show that every planar graph G with girth at least 5 has χ Σ (G) ≤ 19, and for girth at least 6, 7, and 26, χ Σ (G) is at most 9, 8, and 3, respectively. In 2009, Czerwiński, Grytczuk, and Żelazny conjectured that χ Σ (G) ≤ χ(G), where χ(G) is the chromatic number of G. Our result for the class of non-bipartite planar graphs of girth at least 26 is best possible and affirms the conjecture for this class of graphs.

Abstract

Let H be a graph. A decomposition of H is a set of edge-disjoint subgraphs of H whose union is H. A Hamiltonian path (respectively, cycle) of H is a path (respectively, cycle) that contains every vertex of H exactly once. A k-star, denoted by S k, is a star with k edges. In this paper, we give necessary and sufficient conditions for decomposing the complete graph into α copies of Hamiltonian path (cycle) and β copies of S 3.

Abstract

The edit distance function of a hereditary property 𝒣 is the asymptotically largest edit distance between a graph of density p ∈ [0, 1] and 𝒣. Denote by P n and C n the path graph of order n and the cycle graph of order n, respectively. Let C2n* be the cycle graph C 2 n with a diagonal, and C˜n be the graph with vertex set {v 0, v 1, . . . , v n −1} and E(C˜n)=E(Cn){v0v2}. Marchant and Thomason determined the edit distance function of C6*. Peck studied the edit distance function of C n, while Berikkyzy et al. studied the edit distance of powers of cycles. In this paper, by using the methods of Peck and Martin, we determine the edit distance function of C8*, C˜n and P n, respectively.

Abstract

For an integer k at least 2, and a graph G, let f k(G) be the minimum cardinality of a set X of vertices of G such that GX has either k vertices of maximum degree or order less than k. Caro and Yuster [Discrete Mathematics 310 (2010) 742–747] conjectured that, for every k, there is a constant c k such that fk(G)ckn(G) for every graph G. Verifying a conjecture of Caro, Lauri, and Zarb [arXiv:1704.08472v1], we show the best possible result that, if t is a positive integer, and F is a forest of order at most 16(t3+6t2+17t+12), then f 2(F ) ≤ t. We study f 3(F ) for forests F in more detail obtaining similar almost tight results, and we establish upper bounds on f k(G) for graphs G of girth at least 5. For graphs G of girth more than 2p, for p at least 3, our results imply fk(G)=O(n(G)p+13p) . Finally, we show that, for every fixed k, and every given forest F , the value of f k(F ) can be determined in polynomial time.

Abstract

A Roman dominating function on a graph G = (V, E) is a function f:V (G) → {0, 1, 2} such that every vertex u for which f(u) = 0 is adjacent to at least one vertex v with f(v) = 2. The weight of a Roman dominating function is the value w(f) = Σu V(G) f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G, denoted by γR(G). In 2009, Chambers, Kinnersley, Prince and West proved that for any graph G with n vertices and maximum degree Δ, γR(G) ≤ n + 1 − Δ. In this paper, we give a characterization of graphs attaining the previous bound including trees, regular and semiregular graphs. Moreover, we prove that the problem of deciding whether γR(G) = n + 1 − Δ is co-𝒩 𝒫-complete. Finally, we provide a characterization of extremal graphs of a Nordhaus–Gaddum bound for γR(G) + γR (), where is the complement graph of G.

Abstract

In the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree Δ ≤ 4 can be solved in O(n 2) time. This extends Jansen’s result [K. Jansen, The optimum cost chromatic partition problem, in: Proc. CIAC’97, Lecture Notes in Comput. Sci. 1203 (1997) 25–36] for paths and cycles to subgraphs of biquartic graphs.

Abstract

Let S = (a 1,. . . , a m; b 1, . . . , b n), where a 1, . . . , a m and b 1, . . . , b n are two sequences of nonnegative integers. We say that S is a bigraphic pair if there exists a simple bipartite graph G with partite sets {x 1, x 2, . . . , x m} and {y 1, y 2, . . . , y n} such that d G(x i) = a i for 1 ≤ im and d G(y j) = b j for 1 ≤ jn. In this case, we say that G is a realization of S. Analogous to Kundu’s k-factor theorem, we show that if (a 1, a 2, . . . , a m; b 1, b 2, . . . , b n) and (a1 − e1, a2 − e2, . . . , am − em; b1 − f1, b2 − f2, . . . , bn − fn) are two bigraphic pairs satisfying kf ik + 1, 1 ≤ in (or ke ik + 1, 1 ≤ im), for some 0 ≤ km − 1 (or 0 ≤ kn − 1), then (a 1, a 2, . . . , a m; b 1, b 2, . . . , b n) has a realization containing an (e 1, e 2, . . . , e m; f 1, f 2, . . . , f n)-factor. For m = n, we also give a necessary and sufficient condition for an (k n; k n)-factorable bigraphic pair to be connected (k n; k n)-factorable when k ≥ 2. This implies a characterization of bigraphic pairs with a realization containing a Hamiltonian cycle.

Abstract

We prove that an antipodal bipartite graph is a partial cube if and only it is interval monotone. Several characterizations of the principal cycles of an antipodal partial cube are given. We also prove that an antipodal partial cube G is a prism over an even cycle if and only if its order is equal to 4(diam(G) − 1), and that the girth of an antipodal partial cube is less than its diameter whenever it is not a cycle and its diameter is at least equal to 6.