Browse

You are looking at 1 - 10 of 5,214 items for :

  • Mathematics x
Clear All
Open access

Gülnaz Boruzanli Ekinci and John Baptist Gauci

Abstract

A vertex cut of a connected graph G is a set of vertices whose deletion disconnects G. A connected graph G is super-connected if the deletion of every minimum vertex cut of G isolates a vertex. The super-connectivity is the size of the smallest vertex cut of G such that each resultant component does not have an isolated vertex. The Kneser graph KG(n, k) is the graph whose vertices are the k-subsets of {1, 2, . . . , n} and two vertices are adjacent if the k-subsets are disjoint. We use Baranyai’s Theorem on the decompositions of complete hypergraphs to show that the Kneser graph KG are super-connected when n ≥ 5 and that their super-connectivity is n ( n/2) − 6 when n ≥ 6.

Open access

Nader Jafari Rad and Hadi Rahbani

Abstract

For a graph G = (V,E), a double Roman dominating function (or just DRDF) is a function f : V → {0, 1, 2, 3} having the property that if f(v) = 0 for a vertex v, then v has at least two neighbors assigned 2 under f or one neighbor assigned 3 under f, and if f(v) = 1, then vertex v must have at least one neighbor ω with f(ω) ≥ 2. The weight of a DRDF f is the sum f(V ) = Σv∈Vf(v), and the minimum weight of a DRDF on G is the double Roman domination number of G, denoted by γdR(G). In this paper, we derive sharp upper and lower bounds on γdR(G) + γdR(Ḡ) and also γdR(G)γdR(Ḡ) ,where Ḡ is the complement of graph G. We also show that the decision problem for the double Roman domination number is NP- complete even when restricted to bipartite graphs and chordal graphs.

Open access

Roger K. Yeh

Abstract

An L(2, 1)-labeling of a graph G = (V,E) is an assignment of nonnegative integers to V such that two adjacent vertices must receive numbers (labels) at least two apart and further, if two vertices are in distance 2 then they receive distinct labels. This article studies a generalization of the L(2, 1)-labeling. We assign sets with at least one element to vertices of G under some conditions.

Open access

Christopher Duffy, Gary MacGillivray, Pascal Ochem and André Raspaud

Abstract

Brualdi and Quinn Massey [6] defined incidence colouring while study- ing the strong edge chromatic index of bipartite graphs. Here we introduce a similar concept for digraphs and define the oriented incidence chromatic number. Using digraph homomorphisms, we show that the oriented inci- dence chromatic number of a digraph is closely related to the chromatic number of the underlying simple graph. This motivates our study of the oriented incidence chromatic number of symmetric complete digraphs. We give upper and lower bounds for the oriented incidence chromatic number of these graphs, as well as digraphs arising from common graph constructions and decompositions. Additionally we construct, for all k > 2, a target digraph Hkfor which oriented incidence k colouring is equivalent to homomorphism to Hk.

Open access

Janusz Dybizbański and Anna Nenca

Abstract

An oriented coloring of an oriented graph G is a homomorphism from G to H such that H is without selfloops and arcs in opposite directions. We shall say that H is a coloring graph. In this paper, we focus on oriented col- orings of Cartesian products of two paths, called grids, and strong products of two paths, called strong-grids. We show that there exists a coloring graph with nine vertices that can be used to color every orientation of grids with five columns. We also show that there exists a strong-grid with two columns and its orientation which requires 11 colors for oriented coloring. Moreover, we show that every orientation of every strong-grid with three columns can be colored by 19 colors and that every orientation of every strong-grid with four columns can be colored by 43 colors. The above statements were proved with the help of computer programs.

Open access

Thomas M. Lewis

Abstract

The Hamiltonian number of a connected graph is the minimum of the lengths of the closed spanning walks in the graph. In 1968, Grinberg published a necessary condition for the existence of a Hamiltonian cycle in a plane graph, formulated in terms of the degrees of its faces. We show how Grinberg’s theorem can be adapted to provide a lower bound on the Hamiltonian number of a plane graph.

Open access

Xiaodan Chen, Guoliang Hao and Zhihong Xie

Abstract

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S is adjacent from at least one vertex in S. The domination number of a digraph D, denoted by γ(D), is the minimum cardinality of a dominating set of D. A Roman dominating function (RDF) on a digraph D is a function f : V (D) → {0, 1, 2} satisfying the condition that every vertex v with f(v) = 0 has an in-neighbor u with f(u) = 2. The weight of an RDF f is the value ω (f) =Σv∈V(D)f(v). The Roman domination number of a digraph D, denoted by γR(D), is the minimum weight of an RDF on D. In this paper, for any integer k with 2 ≤ k ≤ γ(D), we characterize the digraphs D of order n ≥ 4 with δ(D) ≥ 1 for which γR(D) = (D) + k holds. We also characterize the digraphs D of order n ≥ k with γR(D) = k for any positive integer k. In addition, we present a Nordhaus-Gaddum bound on the Roman domination number of digraphs.

Open access

Chao Yang and Han Ren

Abstract

A set S of vertices of a graph G is called a decycling set if G−S is acyclic. The minimum order of a decycling set is called the decycling number of G, and denoted by ∇(G). Our results include: (a) For any graph G,, where T is taken over all the spanning trees of G and α(G − E(T)) is the independence number of the co-tree G − E(T). This formula implies that computing the decycling number of a graph G is equivalent to finding a spanning tree in G such that its co-tree has the largest independence number. Applying the formula, the lower bounds for the decycling number of some (dense) graphs may be obtained. (b) For any decycling set S of a k-regular graph G, where β(G) = |E(G)|−|V (G)|+1 and m(S) = c+|E(S)|−1, c and |E(S)| are, respectively, the number of components of G − S and the number of edges in G[S]. Hence S is a ∇-set if and only if m(S) is minimum, where∇-set denotes a decycling set containing exactly ∇(G) vertices of G. This provides a new way to locate ∇(G) for k-regular graphs G. (c) 4-regular graphs G with the decycling number are determined.

Open access

Sarbari Mitra and Soumya Bhoumik

Abstract

An L(2, 1)-labeling of a graph Γ is an assignment of non-negative integers to the vertices such that adjacent vertices receive labels that differ by at least 2, and those at a distance of two receive labels that differ by at least one. Let λ1 2(Γ) denote the least λ such that Γ admits an L(2, 1)-labeling using labels from {0, 1, . . . , λ}. A Cayley graph of group G is called a circulant graph of order n, if G = Zn. In this paper initially we investigate the upper bound for the span of the L(2, 1)-labeling for Cayley graphs on cyclic groups with “large” connection sets. Then we extend our observation and find the span of L(2, 1)-labeling for any circulants of order n.

Open access

Yuan Yuan and Rong-Xia Hao

Abstract

Let G be a graph and a, b and k be nonnegative integers with 1 ≤ a ≤ b. A graph G is defined as all fractional (a, b, k)-critical if after deleting any k vertices of G, the remaining graph has all fractional [a, b]-factors. In this paper, we prove that if , then G is all fractional (a, b, k) -critical. If k = 0, we improve the result given in [Filomat 29 (2015) 757-761]. Moreover, we show that this result is best possible in some sense.