Browse

You are looking at 41 - 50 of 88,541 items

Open access

Kefeng Diao, Fuliang Lu and Ping Zhao

Abstract

Let S be a finite set of positive integers. A mixed hypergraph ℋ is a onerealization of S if its feasible set is S and each entry of its chromatic spectrum is either 0 or 1. The minimum number of vertices, denoted by δ 3(S), in a 3-uniform bi-hypergraph which is a one-realization of S was determined in [P. Zhao, K. Diao and F. Lu, More result on the smallest one-realization of a given set, Graphs Combin. 32 (2016) 835–850]. In this paper, we consider the minimum number of edges in a 3-uniform bi-hypergraph which already has the minimum number of vertices with respect of being a minimum bihypergraph that is one-realization of S. A tight lower bound on the number of edges in a 3-uniform bi-hypergraph which is a one-realization of S with δ 3(S) vertices is given.

Open access

Allan Bickle and Allen Schwenk

Abstract

Plesnik proved that the edge connectivity and minimum degree are equal for diameter 2 graphs. We provide a streamlined proof of this fact and characterize the diameter 2 graphs with a nontrivial minimum edge cut.

Open access

Ismail Sahul Hamid and Malairaj Rajeswari

Abstract

Let SV. A vertex vV is a dominator of S if v dominates every vertex in S and v is said to be an anti-dominator of S if v dominates none of the vertices of S. Let 𝒞 = (V 1, V 2, . . ., Vk) be a coloring of G and let vV (G). A color class Vi is called a dom-color class or an anti domcolor class of the vertex v according as v is a dominator of Vi or an antidominator of Vi. The coloring 𝒞 is called a global dominator coloring of G if every vertex of G has a dom-color class and an anti dom-color class in 𝒞. The minimum number of colors required for a global dominator coloring of G is called the global dominator chromatic number and is denoted by χgd(G). This paper initiates a study on this notion of global dominator coloring.

Open access

Majid Hajian and Nader Jafari Rad

Abstract

For k ≥ 1, a k-fair dominating set (or just kFD-set) in a graph G is a dominating set S such that |N(v) ∩ S| = k for every vertex vV \ S. The k-fair domination number of G, denoted by fdk(G), is the minimum cardinality of a kFD-set. A fair dominating set, abbreviated FD-set, is a kFD-set for some integer k ≥ 1. The fair domination number, denoted by fd(G), of G that is not the empty graph, is the minimum cardinality of an FD-set in G. In this paper, aiming to provide a particular answer to a problem posed in [Y. Caro, A. Hansberg and M.A. Henning, Fair domination in graphs, Discrete Math. 312 (2012) 2905–2914], we present a new upper bound for the fair domination number of a cactus graph, and characterize all cactus graphs G achieving equality in the upper bound of fd 1(G).

Open access

Robert F. Bailey and Ismael G. Yero

Abstract

We demonstrate a construction of error-correcting codes from graphs by means of k-resolving sets, and present a decoding algorithm which makes use of covering designs. Along the way, we determine the k-metric dimension of grid graphs (i.e., Cartesian products of paths).

Open access

Nastaran Haghparast and Dariush Kiani

Abstract

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Jackson and Yoshimoto showed that if G is a 3-edge-connected graph with |G| ≥ 5 and v is a vertex with degree 3, then G has an even factor F containing two given edges incident with v in which each component has order at least 5. We prove that this theorem is satisfied for each pair of adjacent edges. Also, we show that each 3-edge-connected graph has an even factor F containing two given edges e and f such that every component containing neither e nor f has order at least 5. But we construct infinitely many 3-edge-connected graphs that do not have an even factor F containing two arbitrary prescribed edges in which each component has order at least 5.

Open access

Jing Wang, Zhangdong Ouyang and Yuanqiu Huang

Abstract

In [C. Thomassen, Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface, Trans. Amer. Math. Soc. 323 (1991) 605–635], Thomassen described completely all (except finitely many) regular tilings of the torus S 1 and the Klein bottle N 2 into (3,6)-tilings, (4,4)-tilings and (6,3)-tilings. Many authors made great efforts to investigate the crossing number (in the plane) of the Cartesian product of an m-cycle and an n-cycle, which is a special (4,4)-tiling. For other tilings, there are quite rare results concerning on their crossing numbers. This motivates us in the paper to determine the crossing number of a hexagonal graph H 3, n, which is a special kind of (3,6)-tilings.

Open access

D. Pillone

Abstract

For a graph G = (V, E), a function f : V (G) → {1, 2, . . ., k} is a kranking for G if f(u) = f(v) implies that every uv path contains a vertex w such that f(w) > f(u). A minimal k-ranking, f, of a graph, G, is a k-ranking with the property that decreasing the label of any vertex results in the ranking property being violated. The rank number χr(G) and the arank number ψr(G) are, respectively, the minimum and maximum value of k such that G has a minimal k-ranking. This paper establishes an upper bound for ψr of a tree and shows the bound is sharp for perfect k-ary trees.

Open access

Brahim Benmedjdoub, Isma Bouchemakh and Éric Sopena

Abstract

A 2-distance k-coloring of a graph G is a mapping from V (G) to the set of colors {1,. . ., k} such that every two vertices at distance at most 2 receive distinct colors. The 2-distance chromatic number χ 2(G) of G is then the smallest k for which G admits a 2-distance k-coloring. For any finite set of positive integers D = {d 1, . . ., d}, the integer distance graph G = G(D) is the infinite graph defined by V (G) = ℤ and uvE(G) if and only if |vu| ∈ D. We study the 2-distance chromatic number of integer distance graphs for several types of sets D. In each case, we provide exact values or upper bounds on this parameter and characterize those graphs G(D) with χ2(G(D)) = ∆(G(D)) + 1.

Open access

Robert A. Beeler, Teresa W. Haynes and Kyle Murphy

Abstract

Let G be a graph with vertex set V and a distribution of pebbles on the vertices of V. A pebbling move consists of removing two pebbles from a vertex and placing one pebble on a neighboring vertex, and a rubbling move consists of removing a pebble from each of two neighbors of a vertex v and placing a pebble on v. We seek an initial placement of a minimum total number of pebbles on the vertices in V, so that no vertex receives more than one pebble and for any given vertex vV, it is possible, by a sequence of pebbling and rubbling moves, to move at least one pebble to v. This minimum number of pebbles is the 1-restricted optimal rubbling number. We determine the 1-restricted optimal rubbling numbers for Cartesian products. We also present bounds on the 1-restricted optimal rubbling number.