Browse

You are looking at 1 - 10 of 4,814 items for :

  • Mathematics x
Clear All
Open access

Henry Liu and Teresa Sousa

Abstract

Given a graph H, the Turán function ex(n,H) is the maximum number of edges in a graph on n vertices not containing H as a subgraph. For two graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let ϕ (n,H) be the smallest number ϕ such that any graph G of order n admits an H-decomposition with at most ϕ parts. Pikhurko and Sousa conjectured that ϕ (n,H) = ex(n,H) for χ (H) ≥ 3 and all sufficiently large n. Their conjecture has been verified by Özkahya and Person for all edge-critical graphs H. In this article, we consider the gem graphs gem4 and gem5. The graph gem4 consists of the path P 4 with four vertices a, b, c, d and edges ab, bc, cd plus a universal vertex u adjacent to a, b, c, d, and the graph gem5 is similarly defined with the path P 5 on five vertices. We determine the Turán functions ex(n, gem4) and ex(n, gem5), and verify the conjecture of Pikhurko and Sousa when H is the graph gem4 and gem5.

Open access

Liying Kang and Erfang Shan

Abstract

A subtree S of a tree T is a central subtree of T if S has the minimum eccentricity in the join-semilattice of all subtrees of T. Among all subtrees lying in the join-semilattice center, the subtree with minimal size is called the least central subtree. Hamina and Peltola asked what is the characterization of trees with unique least central subtree? In general, it is difficult to characterize completely the trees with unique least central subtree. Nieminen and Peltola [The subtree center of a tree, Networks 34 (1999) 272–278] characterized the trees with the least central subtree consisting just of a single vertex. This paper characterizes the trees having two adjacent vertices as a unique least central subtree.

Open access

Michelle Edwards, Gary MacGillivray and Shahla Nasserasr

Abstract

We consider γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. We answer three open questions about γ- graphs of trees by providing upper bounds on the maximum degree, the diameter, and the number of minimum dominating sets. The latter gives an upper bound on the order of the γ-graph.

Open access

Zoran Stanić

Abstract

In this paper we consider the behaviour of the largest eigenvalue (also called the index) of signed graphs under small perturbations like adding a vertex, adding an edge or changing the sign of an edge. We also give a partial ordering of signed cacti with common underlying graph by their indices and demonstrate a general method for obtaining lower and upper bounds for the index. Finally, we provide our computational results related to the generation of small signed graphs.

Open access

Rikio Ichishima, Susana-Clara López, Francesc Antoni Muntaner-Batle and Akito Oshima

Abstract

The beta-number, β (G), of a graph G is defined to be either the smallest positive integer n for which there exists an injective function f : V (G) → {0, 1, . . . , n} such that each uv ∈ E (G) is labeled |f (u) − f (v)| and the resulting set of edge labels is {c, c + 1, . . . , c + |E (G)| − 1} for some positive integer c or +∞ if there exists no such integer n. If c = 1, then the resulting beta-number is called the strong beta-number of G and is denoted by βs (G). In this paper, we show that if G is a bipartite graph and m is odd, then β (mG) ≤ (G) + m − 1. This leads us to conclude that β (mG) = m|V (G)|−1 if G has the additional property that G is a graceful nontrivial tree. In addition to these, we examine the (strong) beta-number of forests whose components are isomorphic to either paths or stars.

Open access

Sahar A. Aleid, José Cáceres and María Luz Puertas

Abstract

An [1, k]-set S in a graph G is a dominating set such that every vertex not in S has at most k neighbors in it. If the additional requirement that the set must be independent is added, the existence of such sets is not guaranteed in every graph. In this paper we solve some problems previously posed by other authors about independent [1, 2]-sets. We provide a necessary condition for a graph to have an independent [1, 2]-set, in terms of spanning trees, and we prove that this condition is also sufficient for cactus graphs. We follow the concept of excellent tree and characterize the family of trees such that any vertex belongs to some independent [1, 2]-set. Finally, we describe a linear algorithm to decide whether a tree has an independent [1, 2]-set. This algorithm can be easily modified to obtain the cardinality of a smallest independent [1, 2]-set of a tree.

Open access

Iztok Peterin, Jens Schreyer, Erika Fecková Škrabul’áková and Andrej Taranenko

Abstract

A sequence is called non-repetitive if none of its subsequences forms a repetition (a sequence r 1 r 2r 2 n such that ri = rn + i for all 1 ≤ in). Let G be a graph whose vertices are coloured. A colouring ϕ of the graph G is non-repetitive if the sequence of colours on every path in G is non-repetitive. The Thue chromatic number, denoted by π(G), is the minimum number of colours of a non-repetitive colouring of G.

In this short note we present two general upper bounds for the Thue chromatic number for the lexicographic product GH of graphs G and H with respect to some properties of the factors. One upper bound is then used to derive the exact values for π(GH) when G is a complete multipartite graph and H an arbitrary graph.

Open access

Pavel Hrnčiar and Gabriela Monoszová

Abstract

The paper deals with Hamiltonian and pancyclic graphs in the class of all self-centered graphs of radius 2. For both of the two considered classes of graphs we have done the following. For a given number n of vertices, we have found an upper bound of the minimum size of such graphs. For n ≤ 12 we have found the exact values of the minimum size. On the other hand, the exact value of the maximum size has been found for every n. Moreover, we have shown that such a graph (of order n and) of size m exists for every m between the minimum and the maximum size. For n ≤ 10 we have found all nonisomorphic graphs of the minimum size, and for n = 11 only for Hamiltonian graphs.

Open access

Amari Bedrane and Berrachedi Abdelhafid

Abstract

A projection of a vertex x of a graph G over a subset S of vertices is a vertex of S at minimal distance from x. The study of projections over quasi-intervals gives rise to a new characterization of quasi-median graphs.

Open access

Joanna Górska, Zdzisław Skupień, Zyta Dziechcińska-Halamoda, Zofia Majcher and Jerzy Michael

Abstract

A digraph is called irregular if its distinct vertices have distinct degree pairs. An irregular digraph is called minimal (maximal) if the removal of any arc (addition of any new arc) results in a non-irregular digraph. It is easily seen that the minimum sizes among irregular n-vertex whether digraphs or oriented graphs are the same and are asymptotic to (√2/3) n 3 / 2; maximum sizes, however, are asymptotic to n 2 and n 2 /2, respectively. Let s stand for the sum of initial positive integers, s = 1, 3, 6, . . . . An oriented graph Hs and a digraph Fs, both large (in terms of the size), minimal irregular, and on any such s vertices, s ≥ 21, are constructed in [Large minimal irregular digraphs, Opuscula Math. 23 (2003) 21–24], co-authored by Z. D-H. and three more of the present co-authors (Z.M., J.M., Z.S.). In the present paper we nearly complete these constructions. Namely, a large minimal irregular digraph Fn, respectively oriented graph Hn, are constructed for any of remaining orders n, n > 21, and of size asymptotic to n 2, respectively to n 2 /2. Also a digraph Φ n and an oriented graph Gn, both small maximal irregular of any order n ≥ 6, are constructed. The asymptotic value of the size of Gn is at least (√2/3) n 3 / 2 and is just the least if n = s → ∞, but otherwise the value is at most four times larger and is just the largest if n = s − 1 → ∞. On the other hand, the size of Φn is of the asymptotic order Θ (n 3 / 2).