1,721,010 research outputs found
Effects of graph operations on star pairwise compatibility graphs
Get PDFA graph
is defined as a star-
-pairwise compatibility graph (PCG) when it is possible to assign a positive real number weight
to each vertex
, and define
distinct intervals
, in such a way that there is an edge
in
if and only if the sum of the weights of vertices
and
falls within the union of these intervals. The star-
-PCG class is connected to two significant graph categories: PCGs and multithreshold graphs. The star number of a graph
, is the smallest
for which
is a star-
-PCG. In this paper, we study the effects of various graph operations, such as the addition of twins, pendant vertices, universal vertices, or isolated vertices, on the star number of the graph resulting from these operations. As significant applications of our findings, we determine the star number of lobster graphs and provide an upper bound for the star number of acyclic graphs. This is particularly interesting as determining the star number is notoriously difficult and is known only for a few classes of graphs. Indeed, for acyclic graphs, the exact value of the star number is currently known only for caterpillars [1]
All graphs with at most seven vertices are Pairwise compatibility graphs
No full textA graph G is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a vertex u∈V and there is an edge (u, v)∈E if and only if dmin ≤ dT,w (lu, lv) ≤ dmax, where dT,w (lu, lv) is the sum of the weights of the edges on the unique path from lu to lv in T. In this note, we show that all the graphs with at most seven vertices are PCGs. In particular, all these graphs except for the wheel on seven vertices W 7 are PCGs of a particular structure of a tree: a centipede. © 2012 The Author 2012. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved
L(2,1)-labeling of oriented planar graphs
Get PDFThe L(2, 1)-labeling of a digraph D is a function l from the vertex set of D to the set of all nonnegative integers such that vertical bar l(x) - l(y)vertical bar >= 2 if x and y are at distance 1, and l(x) not equal l(y) if x and y are at distance 2, where the distance from vertex x to vertex y is the length of a shortest dipath from x to y. The minimum over all the L(2, 1)-labelings of D of the maximum used label is denoted (lambda) over right arrow (D). If C is a class of digraphs, the maximum (lambda) over right arrow (D), over all D is an element of C is denoted (lambda) over right arrow (C). In this paper we study the L(2, 1)-labeling problem on oriented planar graphs providing some upper bounds on (lambda) over right arrow. Then we focus on some specific subclasses of oriented planar graphs, improving the previous general bounds. Namely, for oriented prisms we compute the exact value of (lambda) over right arrow, while for oriented Halin graphs and cacti we provide very close upper and lower bounds for (lambda) over right arrow. (c) 2012 Elsevier B.V. All rights reserved.The L(2,1)-labeling of a digraph D is a function l from the vertex set of D to the set of all nonnegative integers such that |l(x)-l(y)|>=2 if x and y are at distance 1, and l(x)l(y) if x and y are at distance 2, where the distance from vertex x to vertex y is the length of a shortest dipath from x to y. The minimum over all the L(2,1)-labelings of D of the maximum used label is denoted @l->(D). If C is a class of digraphs, the maximum @l->(D), over all D@?C is denoted @l->(C). In this paper we study the L(2,1)-labeling problem on oriented planar graphs providing some upper bounds on @l->. Then we focus on some specific subclasses of oriented planar graphs, improving the previous general bounds. Namely, for oriented prisms we compute the exact value of @l->, while for oriented Halin graphs and cacti we provide very close upper and lower bounds for @l->
On star-multi-interval pairwise compatibility graphs
No full textA graph G is a star-k-PCG if there exists a non-negative edge weighted star tree S and k mutually exclusive intervals I1,I2,...,Ik
of non-negative reals such that each vertex of G corresponds to a leaf of S and there is an edge between two vertices in G if the distance between their corresponding leaves in S lies in I1∪I2∪...∪Ik
. These graphs are related to different well-studied classes of graphs such as PCGs and multithreshold graphs. It is well known that for any graph G there exists a k such that G is a star-k-PCG. Thus, for a given graph G it is interesting to know which is the minimum k such that G is a star-k-PCG.
In this paper, we focus on classes of graphs where k is constant and prove that circular graphs and two dimensional grid graphs are both star-2-PCGs and that they are not star-1-PCGs. Moreover we show that 4-dimensional grids are not star-2-PCG
Oriented L(2, 1)-labeling of planar graphs
No full textIn this paper we study the L(2, 1)-labeling problem on oriented planar graphs with particular attention to the subclasses of oriented prisms, Halin and cacti
Rainbow graph splitting
No full textGiven an integer c, an edge colored graph G is said to be rainbow c-splittable if it can be decomposed into at most c vertex-disjoint monochromatic induced subgraphs of distinct colors. We provide a polynomial-time algorithm for deciding whether an edge-colored complete graph is rainbow c-splittable. For not necessarily complete graphs, we show that the problem is polynomial if c = 2, whereas for c >= 3 it is NP-complete even if the graph has maximum degree 2c - 1. Finally, it remains NP-complete even for 2-edge colored graphs of maximum degree 7c - 14. (C) 2011 Elsevier B.V. All rights reserved
- …
