**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**63

# Search results for: Vertices

##### 63 Natural Emergence of a Core Structure in Networks via Clique Percolation

**Authors:**
A. Melka,
N. Slater,
A. Mualem,
Y. Louzoun

**Abstract:**

**Keywords:**
Networks,
cliques,
percolation,
core structure,
phase
transition.

##### 62 Application of Rapidly Exploring Random Tree Star-Smart and G2 Quintic Pythagorean Hodograph Curves to the UAV Path Planning Problem

**Authors:**
Luiz G. Véras,
Felipe L. Medeiros,
Lamartine F. Guimarães

**Abstract:**

**Keywords:**
Path planning,
path smoothing,
Pythagorean
hodograph curve,
RRT*-Smart.

##### 61 Total Chromatic Number of Δ-Claw-Free 3-Degenerated Graphs

**Authors:**
Wongsakorn Charoenpanitseri

**Abstract:**

**Keywords:**
Total colorings,
the total chromatic number,
3-degenerated.

##### 60 An Improved Method to Compute Sparse Graphs for Traveling Salesman Problem

**Authors:**
Y. Wang

**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*(*CN*_{max}*n*^{2}) where *C* is the iterations, *N*_{max} 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 5*n* 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.

**Keywords:**
Frequency quadrilateral,
iterative algorithm,
sparse graph,
traveling salesman problem.

##### 59 On Chvátal’s Conjecture for the Hamiltonicity of 1-Tough Graphs and Their Complements

**Authors:**
Shin-Shin Kao,
Yuan-Kang Shih,
Hsun Su

**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.

**Keywords:**
Complement,
degree sum,
Hamiltonian,
tough.

##### 58 Efficient Filtering of Graph Based Data Using Graph Partitioning

**Authors:**
Nileshkumar Vaishnav,
Aditya Tatu

**Abstract:**

**Keywords:**
Graph signal processing,
graph partitioning,
inverse
filtering on graphs,
algebraic signal processing.

##### 57 A Minimum Spanning Tree-Based Method for Initializing the K-Means Clustering Algorithm

**Authors:**
J. Yang,
Y. Ma,
X. Zhang,
S. Li,
Y. Zhang

**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.

**Keywords:**
Degree,
initial cluster center,
k-means,
minimum spanning tree.

##### 56 3D Object Model Reconstruction Based on Polywogs Wavelet Network Parametrization

**Authors:**
Mohamed Othmani,
Yassine Khlifi

**Abstract:**

**Keywords:**
3D object,
optimization,
parametrization,
Polywog
wavelets,
reconstruction,
wavelet networks.

##### 55 Computing Maximum Uniquely Restricted Matchings in Restricted Interval Graphs

**Authors:**
Swapnil Gupta,
C. Pandu Rangan

**Abstract:**

**Keywords:**
Uniquely restricted matching,
interval graph,
design
and analysis of algorithms,
matching,
induced matching,
witness
counting.

##### 54 3D Mesh Coarsening via Uniform Clustering

**Authors:**
Shuhua Lai,
Kairui Chen

**Abstract:**

**Keywords:**
Coarsening,
mesh clustering,
shape approximation,
mesh simplification.

##### 53 Building an Arithmetic Model to Assess Visual Consistency in Townscape

**Authors:**
Dheyaa Hussein,
Peter Armstrong

**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.

**Keywords:**
Townscape,
Urban Design,
Visual Assessment,
Visual Consistency.

##### 52 Malware Beaconing Detection by Mining Large-scale DNS Logs for Targeted Attack Identification

**Authors:**
Andrii Shalaginov,
Katrin Franke,
Xiongwei Huang

**Abstract:**

**Keywords:**
Malware detection,
network security,
targeted attack.

##### 51 Hamiltonian Related Properties with and without Faults of the Dual-Cube Interconnection Network and Their Variations

**Authors:**
Shih-Yan Chen,
Shin-Shin Kao

**Abstract:**

**Keywords:**
Hypercubes,
dual-cubes,
fault-tolerant
hamiltonian property,
dual-cube extensive networks,
dual-cube-like
networks.

##### 50 Exploring Counting Methods for the Vertices of Certain Polyhedra with Uncertainties

**Authors:**
Sammani Danwawu Abdullahi

**Abstract:**

*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.

**Keywords:**
Approximation,
counting with uncertainties,
mathematical programming,
optimization,
vertex enumeration.

##### 49 GPU-Accelerated Triangle Mesh Simplification Using Parallel Vertex Removal

**Authors:**
Thomas Odaker,
Dieter Kranzlmueller,
Jens Volkert

**Abstract:**

**Keywords:**
Computer graphics,
half edge collapse,
mesh
simplification,
precomputed simplification,
topology preserving.

##### 48 A Further Study on the 4-Ordered Property of Some Chordal Ring Networks

**Authors:**
Shin-Shin Kao,
Hsiu-Chunj Pan

**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.

**Keywords:**
Hamiltonian cycle,
4-ordered,
Chordal rings,
3-regular.

##### 47 A Genetic Based Algorithm to Generate Random Simple Polygons Using a New Polygon Merge Algorithm

**Authors:**
Ali Nourollah,
Mohsen Movahedinejad

**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.

**Keywords:**
Divide and conquer,
genetic algorithm,
merge
polygons,
Random simple polygon generation.

##### 46 Eccentric Connectivity Index, First and Second Zagreb Indices of Corona Graph

**Authors:**
A. Kulandai Therese

**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.

**Keywords:**
Corona graph,
Degree,
Eccentricity,
Eccentric
Connectivity Index,
First Zagreb index,
Second Zagreb index and
Subdivision graphs.

##### 45 Allocation of Mobile Units in an Urban Emergency Service System

**Authors:**
Dimitra Alexiou

**Abstract:**

In an urban area the location allocation of emergency services mobile units, such as ambulances, police patrol cars must be designed so as to achieve a prompt response to demand locations. In this paper the partition of a given urban network into distinct sub-networks is performed such that the vertices in each component are close and simultaneously the sums of the corresponding population in the sub-networks are almost uniform. The objective here is to position appropriately in each sub-network a mobile emergency unit in order to reduce the response time to the demands. A mathematical model in framework of graph theory is developed. In order to clarify the corresponding method a relevant numerical example is presented on a small network.

**Keywords:**
Distances,
Emergency Service,
Graph Partition,
location.

##### 44 Holomorphic Prioritization of Sets within Decagram of Strategic Decision Making of POSM Using Operational Research (OR): Analytic Hierarchy Process (AHP) Analysis

**Authors:**
Elias O. Tembe,
Hussain A. Al-Salamin

**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.

**Keywords:**
AHP analysis,
Decagram,
Decagon,
Holomorphic.

##### 43 On Chromaticity of Wheels

**Authors:**
Zainab Yasir Al-Rekaby,
Abdul Jalil M. Khalaf

**Abstract:**

Let the vertices of a graph such that every two adjacent vertices have different color is a very common problem in the graph theory. This is known as proper coloring of graphs. The possible number of different proper colorings on a graph with a given number of colors can be represented by a function called the chromatic polynomial. Two graphs G and H are said to be chromatically equivalent, if they share the same chromatic polynomial. A Graph G is chromatically unique, if G is isomorphic to H for any graph H such that G is chromatically equivalent to H. The study of chromatically equivalent and chromatically unique problems is called chromaticity. This paper shows that a wheel W12 is chromatically unique.

**Keywords:**
Chromatic Polynomial,
Chromatically Equivalent,
Chromatically Unique,
Wheel.

##### 42 An Advanced Nelder Mead Simplex Method for Clustering of Gene Expression Data

**Authors:**
M. Pandi,
K. Premalatha

**Abstract:**

The DNA microarray technology concurrently monitors the expression levels of thousands of genes during significant biological processes and across the related samples. The better understanding of functional genomics is obtained by extracting the patterns hidden in gene expression data. It is handled by clustering which reveals natural structures and identify interesting patterns in the underlying data. In the proposed work clustering gene expression data is done through an Advanced Nelder Mead (ANM) algorithm. Nelder Mead (NM) method is a method designed for optimization process. In Nelder Mead method, the vertices of a triangle are considered as the solutions. Many operations are performed on this triangle to obtain a better result. In the proposed work, the operations like reflection and expansion is eliminated and a new operation called spread-out is introduced. The spread-out operation will increase the global search area and thus provides a better result on optimization. The spread-out operation will give three points and the best among these three points will be used to replace the worst point. The experiment results are analyzed with optimization benchmark test functions and gene expression benchmark datasets. The results show that ANM outperforms NM in both benchmarks.

**Keywords:**
Spread out,
simplex,
multi-minima,
fitness function,
optimization,
search area,
monocyte,
solution,
genomes.

##### 41 Nullity of t-Tupple Graphs

**Authors:**
Khidir R. Sharaf,
Didar A. Ali

**Abstract:**

The nullity η(G) of a graph is the occurrence of zero as an eigenvalue in its spectra. A zero-sum weighting of a graph G is real valued function, say f from vertices of G to the set of real numbers, provided that for each vertex of G the summation of the weights f(w) over all neighborhood w of v is zero for each v in G.A high zero-sum weighting of G is one that uses maximum number of non-zero independent variables. If G is graph with an end vertex, and if H is an induced subgraph of G obtained by deleting this vertex together with the vertex adjacent to it, then, η(G)= η(H). In this paper, a high zero-sum weighting technique and the endvertex procedure are applied to evaluate the nullity of t-tupple and generalized t-tupple graphs are derived and determined for some special types of graphs,

Also, we introduce and prove some important results about the t-tupple coalescence, Cartesian and Kronecker products of nut graphs.

**Keywords:**
Graph theory,
Graph spectra,
Nullity of graphs.

##### 40 The Vertex and Edge Irregular Total Labeling of an Amalgamation of Two Isomorphic Cycles

**Authors:**
Nurdin

**Abstract:**

Suppose G(V,E) is a graph, a function f : V \cup E \to \{1, 2, 3, \cdots, k\} is called the total edge(vertex) irregular k-labelling for G such that for each two edges are different having distinct weights. The total edge(vertex) irregularity strength of G, denoted by tes(G)(tvs(G), is the smallest k positive integers such that G has a total edge(vertex) irregular k-labelling. In this paper, we determined the total edge(vertex) irregularity strength of an amalgamation of two isomorphic cycles. The total edge irregularity strength and the total vertex irregularity strength of two isomorphic cycles on n vertices are \lceil (2n+2)/3 \rceil and \lceil 2n/3 \rceil for n \geq 3, respectively.

**Keywords:**
Amalgamation of graphs,
irregular labelling,
irregularity strength.

##### 39 A New Effective Local Search Heuristic for the Maximum Clique Problem

**Authors:**
S. Balaji

**Abstract:**

An edge based local search algorithm, called ELS, is proposed for the maximum clique problem (MCP), a well-known combinatorial optimization problem. ELS is a two phased local search method effectively £nds the near optimal solutions for the MCP. A parameter ’support’ of vertices de£ned in the ELS greatly reduces the more number of random selections among vertices and also the number of iterations and running times. Computational results on BHOSLIB and DIMACS benchmark graphs indicate that ELS is capable of achieving state-of-the-art-performance for the maximum clique with reasonable average running times.

**Keywords:**
Maximum clique,
local search,
heuristic,
NP-complete.

##### 38 Terminal Wiener Index for Graph Structures

**Authors:**
J. Baskar Babujee,
J. Senbagamalar,

**Abstract:**

The topological distance between a pair of vertices i and j, which is denoted by d(vi, vj), is the number of edges of the shortest path joining i and j. The Wiener index W(G) is the sum of distances between all pairs of vertices of a graph G. W(G) = i

**Keywords:**
Graph,
Degree,
Distance,
Pendent vertex,
Wiener index,
Tree.

##### 37 Image Segment Matching Using Affine- Invariant Regions

**Authors:**
Ibrahim El rube'

**Abstract:**

**Keywords:**
Image matching,
key point detection,
affine
invariant,
triangle-shaped segments.

##### 36 The Frequency Graph for the Traveling Salesman Problem

**Authors:**
Y. Wang

**Abstract:**

**Keywords:**
Traveling salesman problem,
frequency graph,
local
optimal Hamiltonian path,
four vertices and three lines inequality.

##### 35 ROI Based Embedded Watermarking of Medical Images for Secured Communication in Telemedicine

**Authors:**
Baisa L. Gunjal,
Suresh N. Mali

**Abstract:**

Medical images require special safety and confidentiality because critical judgment is done on the information provided by medical images. Transmission of medical image via internet or mobile phones demands strong security and copyright protection in telemedicine applications. Here, highly secured and robust watermarking technique is proposed for transmission of image data via internet and mobile phones. The Region of Interest (ROI) and Non Region of Interest (RONI) of medical image are separated. Only RONI is used for watermark embedding. This technique results in exact recovery of watermark with standard medical database images of size 512x512, giving 'correlation factor' equals to 1. The correlation factor for different attacks like noise addition, filtering, rotation and compression ranges from 0.90 to 0.95. The PSNR with weighting factor 0.02 is up to 48.53 dBs. The presented scheme is non blind and embeds hospital logo of 64x64 size.

**Keywords:**
Compression,
DWT,
ROI,
Scrambling,
Vertices

##### 34 An Efficient Heuristic for the Minimum Connected Dominating Set Problem on Ad Hoc Wireless Networks

**Authors:**
S. Balaji,
N. Revathi

**Abstract:**

**Keywords:**
ad hoc wireless networks,
dominating sets,
unit disk
graphs,
heuristic.