
It has been conjectured that the smallest cardinality
We prove results concerning the construction of perfect neighbourhood sets from irredundant sets which could help to resolve the conjecture and which establish that
In particular, the inequality is proved for claw-free graphs and for any graph which has an ir-set
We introduce and study two new parameters, namely the upper harmonious chromatic number,
We show that the decision problems corresponding to the computation of the upper line-distinguishing and upper harmonious chromatic numbers are NP-complete for general graphs
We then determine
Lastly, we show that
For a graph
In this paper, we consider the following special weighting:
\vspace{0.5cm}
– If
– If
\vspace{0.5cm}
Here we show that every graph which has an irregular assignment also has a consecutive labeling. This concept is extended by considering all consecutive labelings and looking for one that has the smallest maximum, in absolute value, edge weight. This weight is referred to as the consecutive strength. Results parallel to the concept of irregularity strength are presented.
A modification of the Schreier-Sims algorithm is described which builds a permutation group utilising the transitivity of the stabiliser subgroups. Alternating and symmetric groups are recognised by their transitivity, resulting in a greatly improved time to build symmetric and alternating groups.
The algorithm has applications to graph isomorphism and other combinatorial isomorphism algorithms, as well as permutation group algorithms.
Suppose
Let
In this paper, I show that any planar graph with
The domination graph of a digraph is the graph on the same vertices with an edge between two vertices if every other vertex loses to at least one of the two. This note describes which connected graphs are domination graphs of tournaments.
Sharp invariant relationships involving various types of domination numbers are found
between a graph and its line graph.
A well-known problem in domination theory is the long-standing conjecture of V.G. Vizing from 1963 (see [7]) that the domination number of the Cartesian product of two graphs is at least as large as the product of the domination numbers of the individual graphs.
Although limited progress has been made, this problem essentially remains open. The usefulness of a maximum 2-packing in one of the graphs in establishing a lower bound has been recognized for some time.
In this paper, we shall extend this approach so as to take advantage of 2-packings whose membership can be altered in a certain way. This results in an improved lower bound for graphs which have 2-packings of this type.
A graph
Every inflated graph
The minimum cardinalities
The motivation of this paper is that for inflated graphs, it is known that the difference
in the four classes of claw-free graphs, closed claw-free graphs, inflated graphs, and line graphs of bipartite graphs.
Let
A partition
We show that any graph with girth greater than
In this paper, we establish that for arbitrary positive integers k and m, where
A connected graph
A queen on a hexagonal board with hexagonal cells is defined as a piece that moves along three lines, namely along the cells in the same row, up diagonal, or down diagonal. A queen dominates a cell if the cell is in the same line as the queen.
We show that hexagonal boards with
A well-spread sequence is an increasing sequence of distinct positive integers whose pairwise sums are distinct. Some properties of these sequences are discussed.
In this note, we consider finite, undirected, and simple graphs. A subset
A vertex
A block-cactus graph is a graph whose blocks are either complete graphs or cycles, and we speak of a cactus if the complete graphs consist of only one edge.
In our main theorem, we shall show that the minimum dominating set problem of an arbitrary graph can be reduced to its blocks. This theorem provides a linear-time algorithm for determining a minimum dominating set in a block-cactus graph, and thus, it can be seen as a supplement to a linear-time algorithm for finding a minimum dominating set in a cactus, presented by S.T. Hedetniemi, R.C. Laskar, and J. Pfaff in 1986.
For a graph facility or multi-facility location problem, each vertex is typically considered to be the location for one customer or one facility. Typically, the number of facilities is predetermined, and one must optimally locate these facilities so as to minimize some function of the distances between customers and facilities (and, perhaps, of the distances among the facilities). For example, p facility locations (such as, for hospitals or fire stations) might be chosen so as to minimize the maximum or the average distance from a customer to the nearest facility. The problem investigated in this paper considers all of the facilities to be distinct, and we seek to minimize the average customer-to-facility distance, primarily for grid graphs.
Let
In this paper, connected graphs
For two vertices
Moreover, for every strong oriented graph
Furthermore, for every integer
For each vertex
independent sets, irredundant sets, open irredundant sets, and CO-irredundant sets of
There are
1970-2025 CP (Manitoba, Canada) unless otherwise stated.