ON THE GRACEFULNESS OF THE GRAPH P2m,2n Liang, Zhihe; Zuo, Huijuan
Applicable analysis and discrete mathematics,
04/2010, Letnik:
4, Številka:
1
Journal Article
Recenzirano
Let Pa,b denotes a graph obtained by identifying the end vertices of b internally disjoint paths each of length a. Kathiresan conjectured that graph Pa,b is graceful except when a is odd and b = 2 ...(mod 4). In this paper we show that the graph Pa,b is graceful when both a and b are even.
Let T be a tree with m edges. A well-known conjecture of Ringel states that T decomposes
the complete graph $K_{2m+1}$. Graham and Häggkvist conjectured that T also decomposes the complete bipartite ...graph $K_{m,m}$. In this paper we show that there exists an integer n with n ≤(3m - 1)/2 and a tree T₁ with n edges such that T₁ decomposes $K_{2n+1}$ and contains T. We also show that there exists an integer n' with n' ≥ 2m-1 and a tree T₂ with n' edges such that T₂ decomposes $K_{n',n'}$and contains T. In the latter case, we can improve the bound if there exists a prime p such that 3m/2 ≤ p < 2m - 1.
A network is said to have
Sense of Direction when the port labeling satisfies a particular set of global consistency constraints. In this paper we study the link between the topology of a system and ...the number of labels that are necessary to have a Sense of Direction in that system. We consider systems whose topology is a
regular graph and we study the relationship between structural properties of
d-regular graphs and existence of a Sense of Direction which uses exactly
d labels (
minimal SD). In particular, we identify a property (
cycle symmetricity) which we show is a necessary condition for minimal
SD. Among regular graphs, we then focus on
Cayley graphs and we prove that they
always have a minimal Sense of Direction.
In 1990, Acharya and Hegde introduced the concept of strongly
k
-indexable graphs: A
(
p
,
q
)
-graph
G
=
(
V
,
E
)
is said to be
strongly
k
-
indexable if its vertices can be assigned distinct ...numbers
0
,
1
,
2
,
…
,
p
−
1
so that the values of the edges, obtained as the sums of the numbers assigned to their end vertices form an arithmetic progression
k
,
k
+
1
,
k
+
2
,
…
,
k
+
(
q
−
1
)
. When
k
=
1
, a strongly
k
-indexable graph is simply called a strongly indexable graph. In this paper, we report some results on strongly
k
-indexable graphs and give an application of strongly
k
-indexable graphs to
plane geometry, viz;
construction of polygons of same internal angles and sides of distinct lengths.
PDF
