Abstract: Let G = (V,E) be a connected graph and distance
between any two vertices a and b in G is a−b geodesic and is denoted
by d(a, b). A set of vertices W resolves a graph G if each vertex is
uniquely determined by its vector of distances to the vertices in W.
A metric dimension of G is the minimum cardinality of a resolving
set of G. In this paper line graph of honeycomb network has been
derived and then we calculated the metric dimension on line graph
of honeycomb network.
Abstract: Networks are often presented as containing a “core”
and a “periphery.” The existence of a core suggests that some
vertices are central and form the skeleton of the network, to which
all other vertices are connected. An alternative view of graphs is
through communities. Multiple measures have been proposed for
dense communities in graphs, the most classical being k-cliques,
k-cores, and k-plexes, all presenting groups of tightly connected
vertices. We here show that the edge number thresholds for such
communities to emerge and for their percolation into a single dense
connectivity component are very close, in all networks studied. These
percolating cliques produce a natural core and periphery structure.
This result is generic and is tested in configuration models and in
real-world networks. This is also true for k-cores and k-plexes. Thus,
the emergence of this connectedness among communities leading to
a core is not dependent on some specific mechanism but a direct
result of the natural percolation of dense communities.
Abstract: In this paper, we show that the conjecture of Chv tal, which states that any 1-tough graph is either a Hamiltonian graph or its complement contains a specific graph denoted by F, does not hold in general. More precisely, it is true only for graphs with six or seven vertices, and is false for graphs with eight or more vertices. A theorem is derived as a correction for the conjecture.
Abstract: This work approaches the automatic planning of paths
for Unmanned Aerial Vehicles (UAVs) through the application of the
Rapidly Exploring Random Tree Star-Smart (RRT*-Smart) algorithm.
RRT*-Smart is a sampling process of positions of a navigation
environment through a tree-type graph. The algorithm consists of
randomly expanding a tree from an initial position (root node) until
one of its branches reaches the final position of the path to be
planned. The algorithm ensures the planning of the shortest path,
considering the number of iterations tending to infinity. When a
new node is inserted into the tree, each neighbor node of the
new node is connected to it, if and only if the extension of the
path between the root node and that neighbor node, with this new
connection, is less than the current extension of the path between
those two nodes. RRT*-smart uses an intelligent sampling strategy
to plan less extensive routes by spending a smaller number of
iterations. This strategy is based on the creation of samples/nodes
near to the convex vertices of the navigation environment obstacles.
The planned paths are smoothed through the application of the
method called quintic pythagorean hodograph curves. The smoothing
process converts a route into a dynamically-viable one based on the
kinematic constraints of the vehicle. This smoothing method models
the hodograph components of a curve with polynomials that obey
the Pythagorean Theorem. Its advantage is that the obtained structure
allows computation of the curve length in an exact way, without the
need for quadratural techniques for the resolution of integrals.
Abstract: The total chromatic number χ"(G) of a graph G is the
minimum number of colors needed to color the elements (vertices
and edges) of G such that no incident or adjacent pair of elements
receive the same color Let G be a graph with maximum degree Δ(G).
Considering a total coloring of G and focusing on a vertex with
maximum degree. A vertex with maximum degree needs a color and
all Δ(G) edges incident to this vertex need more Δ(G) + 1 distinct
colors. To color all vertices and all edges of G, it requires at least
Δ(G) + 1 colors. That is, χ"(G) is at least Δ(G) + 1. However,
no one can find a graph G with the total chromatic number which
is greater than Δ(G) + 2. The Total Coloring Conjecture states that
for every graph G, χ"(G) is at most Δ(G) + 2. In this paper, we prove that the Total Coloring Conjectur for a
Δ-claw-free 3-degenerated graph. That is, we prove that the total
chromatic number of every Δ-claw-free 3-degenerated graph is at
most Δ(G) + 2.
Abstract: The Traveling salesman problem (TSP) is NP-hard in combinatorial optimization. The research shows the algorithms for TSP on the sparse graphs have the shorter computation time than those for TSP according to the complete graphs. We present an improved iterative algorithm to compute the sparse graphs for TSP by frequency graphs computed with frequency quadrilaterals. The iterative algorithm is enhanced by adjusting two parameters of the algorithm. The computation time of the algorithm is O(CNmaxn2) where C is the iterations, Nmax is the maximum number of frequency quadrilaterals containing each edge and n is the scale of TSP. The experimental results showed the computed sparse graphs generally have less than 5n edges for most of these Euclidean instances. Moreover, the maximum degree and minimum degree of the vertices in the sparse graphs do not have much difference. Thus, the computation time of the methods to resolve the TSP on these sparse graphs will be greatly reduced.
Abstract: An algebraic framework for processing graph signals
axiomatically designates the graph adjacency matrix as the shift
operator. In this setup, we often encounter a problem wherein we
know the filtered output and the filter coefficients, and need to
find out the input graph signal. Solution to this problem using
direct approach requires O(N3) operations, where N is the number
of vertices in graph. In this paper, we adapt the spectral graph
partitioning method for partitioning of graphs and use it to reduce
the computational cost of the filtering problem. We use the example
of denoising of the temperature data to illustrate the efficacy of the
approach.
Abstract: The traditional k-means algorithm has been widely used as a simple and efficient clustering method. However, the algorithm often converges to local minima for the reason that it is sensitive to the initial cluster centers. In this paper, an algorithm for selecting initial cluster centers on the basis of minimum spanning tree (MST) is presented. The set of vertices in MST with same degree are regarded as a whole which is used to find the skeleton data points. Furthermore, a distance measure between the skeleton data points with consideration of degree and Euclidean distance is presented. Finally, MST-based initialization method for the k-means algorithm is presented, and the corresponding time complexity is analyzed as well. The presented algorithm is tested on five data sets from the UCI Machine Learning Repository. The experimental results illustrate the effectiveness of the presented algorithm compared to three existing initialization methods.
Abstract: This paper presents a technique for compact three
dimensional (3D) object model reconstruction using wavelet
networks. It consists to transform an input surface vertices
into signals,and uses wavelet network parameters for signal
approximations. To prove this, we use a wavelet network architecture
founded on several mother wavelet families. POLYnomials
WindOwed with Gaussians (POLYWOG) wavelet families are used
to maximize the probability to select the best wavelets which
ensure the good generalization of the network. To achieve a better
reconstruction, the network is trained several iterations to optimize the
wavelet network parameters until the error criterion is small enough.
Experimental results will shown that our proposed technique can
effectively reconstruct an irregular 3D object models when using
the optimized wavelet network parameters. We will prove that an
accurateness reconstruction depends on the best choice of the mother
wavelets.
Abstract: In this paper, we present a fast and efficient mesh coarsening algorithm for 3D triangular meshes. Theis approach can be applied to very complex 3D meshes of arbitrary topology and with millions of vertices. The algorithm is based on the clustering of the input mesh elements, which divides the faces of an input mesh into a given number of clusters for clustering purpose by approximating the Centroidal Voronoi Tessellation of the input mesh. Once a clustering is achieved, it provides us an efficient way to construct uniform tessellations, and therefore leads to good coarsening of polygonal meshes. With proliferation of 3D scanners, this coarsening algorithm is particularly useful for reverse engineering applications of 3D models, which in many cases are dense, non-uniform, irregular and arbitrary topology. Examples demonstrating effectiveness of the new algorithm are also included in the paper.
Abstract: A uniquely restricted matching is defined to be a
matching M whose matched vertices induces a sub-graph which has
only one perfect matching. In this paper, we make progress on the
open question of the status of this problem on interval graphs (graphs
obtained as the intersection graph of intervals on a line). We give
an algorithm to compute maximum cardinality uniquely restricted
matchings on certain sub-classes of interval graphs. We consider two
sub-classes of interval graphs, the former contained in the latter, and
give O(|E|^2) time algorithms for both of them. It is to be noted that
both sub-classes are incomparable to proper interval graphs (graphs
obtained as the intersection graph of intervals in which no interval
completely contains another interval), on which the problem can be
solved in polynomial time.
Abstract: In this paper, a thorough review about dual-cubes, DCn,
the related studies and their variations are given. DCn was introduced
to be a network which retains the pleasing properties of hypercube Qn
but has a much smaller diameter. In fact, it is so constructed that the
number of vertices of DCn is equal to the number of vertices of Q2n
+1. However, each vertex in DCn is adjacent to n + 1 neighbors and
so DCn has (n + 1) × 2^2n edges in total, which is roughly half the
number of edges of Q2n+1. In addition, the diameter of any DCn is 2n
+2, which is of the same order of that of Q2n+1. For selfcompleteness,
basic definitions, construction rules and symbols are
provided. We chronicle the results, where eleven significant theorems
are presented, and include some open problems at the end.
Abstract: One of the leading problems in Cyber Security today
is the emergence of targeted attacks conducted by adversaries with
access to sophisticated tools. These attacks usually steal senior level
employee system privileges, in order to gain unauthorized access to
confidential knowledge and valuable intellectual property. Malware
used for initial compromise of the systems are sophisticated and
may target zero-day vulnerabilities. In this work we utilize common
behaviour of malware called ”beacon”, which implies that infected
hosts communicate to Command and Control servers at regular
intervals that have relatively small time variations. By analysing
such beacon activity through passive network monitoring, it is
possible to detect potential malware infections. So, we focus on
time gaps as indicators of possible C2 activity in targeted enterprise
networks. We represent DNS log files as a graph, whose vertices
are destination domains and edges are timestamps. Then by using
four periodicity detection algorithms for each pair of internal-external
communications, we check timestamp sequences to identify the
beacon activities. Finally, based on the graph structure, we infer the
existence of other infected hosts and malicious domains enrolled in
the attack activities.
Abstract: The phenomenon of visual disorder is prominent in contemporary townscapes. This paper provides a theoretical framework for the assessment of visual consistency in townscape in order to achieve more favourable outcomes for users. In this paper, visual consistency refers to the amount of similarity between adjacent components of townscape. The paper investigates parameters which relate to visual consistency in townscape, explores the relationships between them and highlights their significance. The paper uses arithmetic methods from outside the domain of urban design to enable the establishment of an objective approach of assessment which considers subjective indicators including users’ preferences. These methods involve the standard of deviation, colour distance and the distance between points. The paper identifies urban space as a key representative of the visual parameters of townscape. It focuses on its two components, geometry and colour in the evaluation of the visual consistency of townscape. Accordingly, this article proposes four measurements. The first quantifies the number of vertices, which are points in the three-dimensional space that are connected, by lines, to represent the appearance of elements. The second evaluates the visual surroundings of urban space through assessing the location of their vertices. The last two measurements calculate the visual similarity in both vertices and colour in townscape by the calculation of their variation using methods including standard of deviation and colour difference. The proposed quantitative assessment is based on users’ preferences towards these measurements. The paper offers a theoretical basis for a practical tool which can alter the current understanding of architectural form and its application in urban space. This tool is currently under development. The proposed method underpins expert subjective assessment and permits the establishment of a unified framework which adds to creativity by the achievement of a higher level of consistency and satisfaction among the citizens of evolving townscapes.
Abstract: Vertex Enumeration Algorithms explore the methods and procedures of generating the vertices of general polyhedra formed by system of equations or inequalities. These problems of enumerating the extreme points (vertices) of general polyhedra are shown to be NP-Hard. This lead to exploring how to count the vertices of general polyhedra without listing them. This is also shown to be #P-Complete. Some fully polynomial randomized approximation schemes (fpras) of counting the vertices of some special classes of polyhedra associated with Down-Sets, Independent Sets, 2-Knapsack problems and 2 x n transportation problems are presented together with some discovered open problems.
Abstract: We present an approach to triangle mesh simplification
designed to be executed on the GPU. We use a quadric error metric
to calculate an error value for each vertex of the mesh and order all
vertices based on this value. This step is followed by the parallel
removal of a number of vertices with the lowest calculated error
values. To allow for the parallel removal of multiple vertices we use
a set of per-vertex boundaries that prevent mesh foldovers even when
simplification operations are performed on neighbouring vertices. We
execute multiple iterations of the calculation of the vertex errors,
ordering of the error values and removal of vertices until either a
desired number of vertices remains in the mesh or a minimum error
value is reached. This parallel approach is used to speed up the
simplification process while maintaining mesh topology and avoiding
foldovers at every step of the simplification.
Abstract: The eccentric connectivity index based on degree and
eccentricity of the vertices of a graph is a widely used graph invariant
in mathematics.
In this paper, we present the explicit eccentric connectivity index,
first and second Zagreb indices for a Corona graph and sub divisionrelated
corona graphs.
Abstract: In this paper a new algorithm to generate random
simple polygons from a given set of points in a two dimensional
plane is designed. The proposed algorithm uses a genetic algorithm to
generate polygons with few vertices. A new merge algorithm is
presented which converts any two polygons into a simple polygon.
This algorithm at first changes two polygons into a polygonal chain
and then the polygonal chain is converted into a simple polygon. The
process of converting a polygonal chain into a simple polygon is
based on the removal of intersecting edges. The experiments results
show that the proposed algorithm has the ability to generate a great
number of different simple polygons and has better performance in
comparison to celebrated algorithms such as space partitioning and
steady growth.
Abstract: Given a graph G. A cycle of G is a sequence of
vertices of G such that the first and the last vertices are the same.
A hamiltonian cycle of G is a cycle containing all vertices of G.
The graph G is k-ordered (resp. k-ordered hamiltonian) if for any
sequence of k distinct vertices of G, there exists a cycle (resp.
hamiltonian cycle) in G containing these k vertices in the specified
order. Obviously, any cycle in a graph is 1-ordered, 2-ordered and 3-
ordered. Thus the study of any graph being k-ordered (resp. k-ordered
hamiltonian) always starts with k = 4. Most studies about this topic
work on graphs with no real applications. To our knowledge, the
chordal ring families were the first one utilized as the underlying
topology in interconnection networks and shown to be 4-ordered.
Furthermore, based on our computer experimental results, it was
conjectured that some of them are 4-ordered hamiltonian. In this
paper, we intend to give some possible directions in proving the
conjecture.
Abstract: There is decagram of strategic decisions of operations
and production/service management (POSM) within operational
research (OR) which must collate, namely: design, inventory, quality,
location, process and capacity, layout, scheduling, maintain ace, and
supply chain. This paper presents an architectural configuration
conceptual framework of a decagram of sets decisions in a form of
mathematical complete graph and abelian graph.
Mathematically, a complete graph is undirected (UDG), and
directed (DG) a relationship where every pair of vertices is
connected, collated, confluent, and holomorphic.
There has not been any study conducted which, however,
prioritizes the holomorphic sets which of POMS within OR field of
study. The study utilizes OR structured technique known as The
Analytic Hierarchy Process (AHP) analysis for organizing, sorting
and prioritizing(ranking) the sets within the decagram of POMS
according to their attribution (propensity), and provides an analysis
how the prioritization has real-world application within the 21st
century.