Graph Theory
Let G = (V,E) be a graph. For each e ∈E(G) and v ∈V(G), let Le and Lv, respectively, be a list of real numbers. Let w be a function on V(G) ∪E(G) such that w(e) ∈Le for each e ∈E(G) and ...w(v) ∈Lv for each v ∈V(G), and let cw be the vertex colouring obtained by cw(v) = w(v) + ∑ₑ ∋vw(e). A graph is (k,l)-weight choosable if there exists a weighting function w for which cw is proper whenever |Lv| ≥k and |Le| ≥l for every v ∈V(G) and e ∈E(G). A sufficient condition for a graph to be (1,l)-weight choosable was developed by Bartnicki, Grytczuk and Niwczyk (2009), based on the Combinatorial Nullstellensatz, a parameter which they call the monomial index of a graph, and matrix permanents. This paper extends their method to establish the first general upper bound on the monomial index of a graph, and thus to obtain an upper bound on l for which every admissible graph is (1,l)-weight choosable. Let ∂2(G) denote the smallest value s such that every induced subgraph of G has vertices at distance 2 whose degrees sum to at most s. We show that every admissible graph has monomial index at most ∂2(G) and hence that such graphs are (1, ∂2(G)+1)-weight choosable. While this does not improve the best known result on (1,l)-weight choosability, we show that the results can be extended to obtain improved bounds for some graph products; for instance, it is shown that G □ Kn is (1, nd+3)-weight choosable if G is d-degenerate.
A notion of real number graph labellings captures the dependence of the span of an optimal channel assignment on the separations that are required between frequencies assigned to close transmitters. ...We determine the spans of such optimal labellings for a subfamily of Kneser graphs formed by the complements of the line graphs of complete graphs. This subfamily contains (among others) the Petersen graph.
Complete graphs in the Rubáiyát May, D.P.
Journal of mathematics and the arts,
9/18/2014, Letnik:
8, Številka:
1-2
Journal Article
Recenzirano
The Rubáiyát of Omar Khayyám has fascinated readers for centuries, and it has been translated and interpreted many times. In this paper, we will describe a few basic graph theory concepts, and ...discuss how graph theory can be used to explore the connections between the various quatrains contained in Edward FitzGerald's several translations of the Rubáiyát. We will explain the process of searching for certain complete subgraphs of the full graph of the Rubáiyát, and will briefly discuss how these ideas may be relevant in other areas. These applications include analysing other collections of poetry, teaching certain types of incidence geometry and poetic forms for composing short collections of poetry.
It is easily shown that every path has a graceful labelling, however, in this paper we show that given almost any path
P
with
n
vertices then for every vertex
v
∈
V
(
P
)
and for every integer
i
∈
{
...0
,
…
,
n
-
1
}
there is a graceful labelling of
P
such that
v
has label
i
. We show precisely when these labellings can also be
α
-labellings. We then extend this result to strong edge-magic labellings. In obtaining these results we make heavy use of
π
-representations of
α
-labellings and review some relevant results of Kotzig and Rosa.
The theory of integer $\lambda$-labellings of a graph, introduced by Griggs and Yeh J. R. Griggs and R. K.-C. Yeh, SIAM J. Discrete Math., 5 (1992), pp. 586-595, seeks to model efficient channel ...assignments for a network of transmitters. To prevent interference, labels for nearby vertices must be separated by specified amounts $k_i$ depending on the distance $i$, $1\le i\le p$. Here we expand the model to allow real number labels and separations. The main finding ("D-Set Theorem") is that for any graph, possibly infinite, with maximum degree at most $\Delta$, there is a labelling of minimum span in which all of the labels have the form $\sum_{i=1}^p a_i k_i$, where the $a_i$'s are integers $\ge0$. We show that the minimum span is a continuous function of the $k_i$'s, and we conjecture that it is piecewise linear with finitely many pieces. Our stronger conjecture is that the coefficients $a_i$ can be bounded by a constant depending only on $\Delta$ and $p$. We offer results in strong support of the conjectures, and we give formulas for the minimum spans of several graphs with general conditions at distance two.
The dual bandwidth of a graph, is the maximum value of the minimum labeling variance of any two adjacent vertices. The computational complexity of finding the dual bandwidth of a general graph is ...Np-complete. Even the problem of deciding whether the dual bandwidth of graph is two or not is Np-complete. Therefore, we consider the dual bandwidth of special graphs- the product of two paths. We find the upper and lower bound of these graphs.
We examine decompositions of complete graphs
K
4
k
+
2
into
2
k
+
1
isomorphic spanning trees. We develop a method of factorization based on a new type of vertex labelling, namely blended
ρ
...-labelling. We also show that for every
k
⩾
1
and every
d
,
3
⩽
d
⩽
4
k
+
1
there is a tree with diameter
d
that decomposes
K
4
k
+
2
into
2
k
+
1
factors isomorphic to
T
.
Coding Graphic Groups For Network Security Zhao, Meimei; Yao, Ming; Zhang, Xiaohui ...
2019 IEEE 4th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC),
2019-Dec.
Conference Proceeding
The overall security is a new topic on network security in Today's digital business. As known, graphical passwords (GPWs) are applied in the world. Topological graphic passwords (Topsnut-gpws) differ ...from the existing GPWs, since they can be expressed by popular matrices and can produce graphic groups for encrypting networks. New coding techniques are introduced and new coding graphic groups and matrix groups are constructed in this article. Some new problems are given for investigating deeply graphic groups and matrix groups.
Graph Edit Distance is the most widely used measure of similarity between attributed graphs. Given a pair of graphs, it obtains a value of their similarity and also a path that transforms one graph ...into the other through edit operations. This path can be expressed as a labelling between nodes of both graphs. Important parameters of this measure are the costs of edit operations. In this article, we present new properties of the Graph Edit Distance and we show that its minimization lead to a few different labellings and so, most of the labellings in the labelling space cannot be obtained. Moreover, we present a method that using some of the new properties of the Graph Edit Distance speeds up the computation of all possible labellings.
PDF
