**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**1051

# Search results for: Distance in graphs

##### 1051 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.

##### 1050 A Study about the Distribution of the Spanning Ratios of Yao Graphs

**Authors:**
Maryam Hsaini,
Mostafa Nouri-Baygi

**Abstract:**

A critical problem in wireless sensor networks is limited battery and memory of nodes. Therefore, each node in the network could maintain only a subset of its neighbors to communicate with. This will increase the battery usage in the network because each packet should take more hops to reach its destination. In order to tackle these problems, spanner graphs are defined. Since each node has a small degree in a spanner graph and the distance in the graph is not much greater than its actual geographical distance, spanner graphs are suitable candidates to be used for the topology of a wireless sensor network. In this paper, we study Yao graphs and their behavior for a randomly selected set of points. We generate several random point sets and compare the properties of their Yao graphs with the complete graph. Based on our data sets, we obtain several charts demonstrating how Yao graphs behave for a set of randomly chosen point set. As the results show, the stretch factor of a Yao graph follows a normal distribution. Furthermore, the stretch factor is in average far less than the worst case stretch factor proved for Yao graphs in previous results. Furthermore, we use Yao graph for a realistic point set and study its stretch factor in real world.

**Keywords:**
Wireless sensor network,
spanner graph,
Yao Graph.

##### 1049 Using Spectral Vectors and M-Tree for Graph Clustering and Searching in Graph Databases of Protein Structures

**Authors:**
Do Phuc,
Nguyen Thi Kim Phung

**Abstract:**

**Keywords:**
Eigenvalues,
m-tree,
graph database,
protein
structure,
spectra graph theory.

##### 1048 On Suborbital Graphs of the Congruence Subgroup r 0(N)

**Authors:**
Bahadir O. Guler,
Serkan Kader,
Murat Besenk

**Abstract:**

**Keywords:**
Congruence subgroup,
Imprimitive action,
Modulargroup,
Suborbital graphs.

##### 1047 All-Pairs Shortest-Paths Problem for Unweighted Graphs in O(n2 log n) Time

**Authors:**
Udaya Kumar Reddy K. R,
K. Viswanathan Iyer

**Abstract:**

Given a simple connected unweighted undirected graph G = (V (G), E(G)) with |V (G)| = n and |E(G)| = m, we present a new algorithm for the all-pairs shortest-path (APSP) problem. The running time of our algorithm is in O(n2 log n). This bound is an improvement over previous best known O(n2.376) time bound of Raimund Seidel (1995) for general graphs. The algorithm presented does not rely on fast matrix multiplication. Our algorithm with slight modifications, enables us to compute the APSP problem for unweighted directed graph in time O(n2 log n), improving a previous best known O(n2.575) time bound of Uri Zwick (2002).

**Keywords:**
Distance in graphs,
Dynamic programming,
Graphalgorithms,
Shortest paths.

##### 1046 Lower Bounds of Some Small Ramsey Numbers

**Authors:**
Decha Samana,
Vites Longani

**Abstract:**

**Keywords:**
Lower bound,
Ramsey numbers,
Graphs,
Distance line.

##### 1045 Graphs with Metric Dimension Two-A Characterization

**Authors:**
Sudhakara G,
Hemanth Kumar A.R

**Abstract:**

In this paper, we define distance partition of vertex set of a graph G with reference to a vertex in it and with the help of the same, a graph with metric dimension two (i.e. β (G) = 2 ) is characterized. In the process, we develop a polynomial time algorithm that verifies if the metric dimension of a given graph G is two. The same algorithm explores all metric bases of graph G whenever β (G) = 2 . We also find a bound for cardinality of any distance partite set with reference to a given vertex, when ever β (G) = 2 . Also, in a graph G with β (G) = 2 , a bound for cardinality of any distance partite set as well as a bound for number of vertices in any sub graph H of G is obtained in terms of diam H .

**Keywords:**
Metric basis,
Distance partition,
Metric dimension.

##### 1044 Isomorphism on Fuzzy Graphs

**Authors:**
A.Nagoor Gani,
J.Malarvizhi

**Abstract:**

**Keywords:**
complementary fuzzy graphs,
co-weak isomorphism,
equivalence relation,
fuzzy relation,
weak isomorphism.

##### 1043 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.

##### 1042 Reductions of Control Flow Graphs

**Authors:**
Robert Gold

**Abstract:**

Control ﬂow graphs are a well-known representation of the sequential control ﬂow structure of programs with a multitude of applications. Not only single functions but also sets of functions or complete programs can be modeled by control ﬂow graphs. In this case the size of the graphs can grow considerably and thus makes it difﬁcult for software engineers to analyze the control ﬂow. Graph reductions are helpful in this situation. In this paper we deﬁne reductions to subsets of nodes. Since executions of programs are represented by paths through the control ﬂow graphs, paths should be preserved. Furthermore, the composition of reductions makes a stepwise analysis approach possible.

**Keywords:**
Control ﬂow graph,
graph reduction.

##### 1041 2D Structured Non-Cyclic Fuzzy Graphs

**Authors:**
T. Pathinathan,
M. Peter

**Abstract:**

**Keywords:**
Double layered fuzzy graph,
double layered non-cyclic fuzzy graph,
strong,
order,
degree and size.

##### 1040 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.

##### 1039 Low Complexity Regular LDPC codes for Magnetic Storage Devices

**Authors:**
Gabofetswe Malema,
Michael Liebelt

**Abstract:**

LDPC codes could be used in magnetic storage devices because of their better decoding performance compared to other error correction codes. However, their hardware implementation results in large and complex decoders. This one of the main obstacles the decoders to be incorporated in magnetic storage devices. We construct small high girth and rate 2 columnweight codes from cage graphs. Though these codes have low performance compared to higher column weight codes, they are easier to implement. The ease of implementation makes them more suitable for applications such as magnetic recording. Cages are the smallest known regular distance graphs, which give us the smallest known column-weight 2 codes given the size, girth and rate of the code.

**Keywords:**
Structured LDPC codes,
cage graphs.

##### 1038 Low Complexity, High Performance LDPC Codes Based on Defected Fullerene Graphs

**Authors:**
Ashish Goswami,
Rakesh Sharma

**Abstract:**

**Keywords:**
LDPC Codes,
Fullerene Graphs,
Defected Fullerene
Graphs.

##### 1037 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.

##### 1036 On Detour Spectra of Some Graphs

**Authors:**
S.K.Ayyaswamy,
S.Balachandran

**Abstract:**

**Keywords:**
Detour eigenvalue (of a graph),
detour spectrum(of a graph),
detour energy(of a graph),
detour - equienergetic graphs.

##### 1035 On Speeding Up Support Vector Machines: Proximity Graphs Versus Random Sampling for Pre-Selection Condensation

**Authors:**
Xiaohua Liu,
Juan F. Beltran,
Nishant Mohanchandra,
Godfried T. Toussaint

**Abstract:**

**Keywords:**
Machine learning,
data mining,
support vector machines,
proximity graphs,
relative-neighborhood graphs,
k-nearestneighbor graphs,
random sampling,
training data condensation.

##### 1034 On Strong(Weak) Domination in Fuzzy Graphs

**Authors:**
C.Natarajan,
S.K.Ayyaswamy

**Abstract:**

Let G be a fuzzy graph. Then D Ôèå V is said to be a strong (weak) fuzzy dominating set of G if every vertex v ∈ V -D is strongly (weakly) dominated by some vertex u in D. We denote a strong (weak) fuzzy dominating set by sfd-set (wfd-set). The minimum scalar cardinality of a sfd-set (wfd-set) is called the strong (weak) fuzzy domination number of G and it is denoted by γsf (G)γwf (G). In this paper we introduce the concept of strong (weak) domination in fuzzy graphs and obtain some interesting results for this new parameter in fuzzy graphs.

**Keywords:**
Fuzzy graphs,
fuzzy domination,
strong (weak) fuzzy domination number.

##### 1033 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.

##### 1032 Diameter of Zero Divisor Graphs of Finite Direct Product of Lattices

**Authors:**
H. Y. Pourali,
V. V. Joshi,
B. N. Waphare.

**Abstract:**

In this paper, we verify the diameter of zero divisor graphs with respect to direct product.

**Keywords:**
Atomic lattice,
complement of graph,
diameter,
direct
product of lattices,
0-distributive lattice,
girth,
product of graphs,
prime ideal,
zero divisor graph.

##### 1031 A Distance Function for Data with Missing Values and Its Application

**Authors:**
Loai AbdAllah,
Ilan Shimshoni

**Abstract:**

Missing values in data are common in real world applications. Since the performance of many data mining algorithms depend critically on it being given a good metric over the input space, we decided in this paper to define a distance function for unlabeled datasets with missing values. We use the Bhattacharyya distance, which measures the similarity of two probability distributions, to define our new distance function. According to this distance, the distance between two points without missing attributes values is simply the Mahalanobis distance. When on the other hand there is a missing value of one of the coordinates, the distance is computed according to the distribution of the missing coordinate. Our distance is general and can be used as part of any algorithm that computes the distance between data points. Because its performance depends strongly on the chosen distance measure, we opted for the k nearest neighbor classifier to evaluate its ability to accurately reflect object similarity. We experimented on standard numerical datasets from the UCI repository from different fields. On these datasets we simulated missing values and compared the performance of the kNN classifier using our distance to other three basic methods. Our experiments show that kNN using our distance function outperforms the kNN using other methods. Moreover, the runtime performance of our method is only slightly higher than the other methods.

**Keywords:**
Missing values,
Distance metric,
Bhattacharyya distance.

##### 1030 Problem Solving in Chilean Higher Education: Figurations Prior in Interpretations of Cartesian Graphs

**Authors:**
Verónica Díaz

**Abstract:**

A Cartesian graph, as a mathematical object, becomes a tool for configuration of change. Its best comprehension is done through everyday life problem-solving associated with its representation. Despite this, the current educational framework favors general graphs, without consideration of their argumentation. Students are required to find the mathematical function without associating it to the development of graphical language. This research describes the use made by students of configurations made prior to Cartesian graphs with regards to an everyday life problem related to a time and distance variation phenomenon. The theoretical framework describes the function conditions of study and their modeling. This is a qualitative, descriptive study involving six undergraduate case studies that were carried out during the first term in 2016 at University of Los Lagos. The research problem concerned the graphic modeling of a real person’s movement phenomenon, and two levels of analysis were identified. The first level aims to identify local and global graph interpretations; a second level describes the iconicity and referentiality degree of an image. According to the results, students were able to draw no figures before the Cartesian graph, highlighting the need for students to represent the context and the movement of which causes the phenomenon change. From this, they managed Cartesian graphs representing changes in position, therefore, achieved an overall view of the graph. However, the local view only indicates specific events in the problem situation, using graphic and verbal expressions to represent movement. This view does not enable us to identify what happens on the graph when the movement characteristics change based on possible paths in the person’s walking speed.

**Keywords:**
Cartesian graphs,
higher education,
movement modeling,
problem solving.

##### 1029 Skolem Sequences and Erdosian Labellings of m Paths with 2 and 3 Vertices

**Authors:**
H. V. Chen

**Abstract:**

**Keywords:**
c-Erdösian,
Skolem sequences,
magic labelling

##### 1028 N-Sun Decomposition of Complete Graphs and Complete Bipartite Graphs

**Authors:**
R. Anitha,
R. S. Lekshmi

**Abstract:**

**Keywords:**
Hamilton cycle,
n-sun decomposition,
perfectmatching,
spanning tree.

##### 1027 Differences in Students` Satisfaction with Distance Learning Studies

**Authors:**
Ana Horvat,
Maja Krsmanovic,
Mladen Djuric

**Abstract:**

**Keywords:**
distance learning,
students' satisfaction

##### 1026 OWA Operators in Generalized Distances

**Authors:**
José M. Merigó,
Anna M. Gil-Lafuente

**Abstract:**

**Keywords:**
Aggregation operators,
Distance measures,
Quasi- OWA operator.

##### 1025 Analyzing Methods of the Relation between Concepts based on a Concept Hierarchy

**Authors:**
Ke Lu,
Tetsuya Furukawa

**Abstract:**

**Keywords:**
Concept Hierarchy,
Horizontal Distance,
Relation
Analysis,
Vertical Distance

##### 1024 A Hamiltonian Decomposition of 5-star

**Authors:**
Walter Hussak,
Heiko Schröder

**Abstract:**

Star graphs are Cayley graphs of symmetric groups of permutations, with transpositions as the generating sets. A star graph is a preferred interconnection network topology to a hypercube for its ability to connect a greater number of nodes with lower degree. However, an attractive property of the hypercube is that it has a Hamiltonian decomposition, i.e. its edges can be partitioned into disjoint Hamiltonian cycles, and therefore a simple routing can be found in the case of an edge failure. The existence of Hamiltonian cycles in Cayley graphs has been known for some time. So far, there are no published results on the much stronger condition of the existence of Hamiltonian decompositions. In this paper, we give a construction of a Hamiltonian decomposition of the star graph 5-star of degree 4, by defining an automorphism for 5-star and a Hamiltonian cycle which is edge-disjoint with its image under the automorphism.

**Keywords:**
interconnection networks,
paths and cycles,
graphs andgroups.

##### 1023 Using the OWA Operator in the Minkowski Distance

**Authors:**
José M. Merigó,
Anna M. Gil-Lafuente

**Abstract:**

**Keywords:**
Aggregation operators,
Minkowski distance,
OWA
operators,
Selection of strategies.

##### 1022 The Distance between a Point and a Bezier Curveon a Bezier Surface

**Authors:**
Wen-Haw Chen,
Sheng-Gwo Chen

**Abstract:**

**Keywords:**
Geodesic-like curve,
distance,
projection,
Bezier.