Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 1543

Search results for: graph angle

1543 Topological Indices of Some Graph Operations

Authors: U. Mary


Let be a graph with a finite, nonempty set of objects called vertices together with a set of unordered pairs of distinct vertices of called edges. The vertex set is denoted by and the edge set by. Given two graphs and the wiener index of, wiener index for the splitting graph of a graph, the first Zagreb index of and its splitting graph, the 3-steiner wiener index of, the 3-steiner wiener index of a special graph are explored in this paper.

Keywords: complementary prism graph, first Zagreb index, neighborhood corona graph, steiner distance, splitting graph, steiner wiener index, wiener index

Procedia PDF Downloads 425
1542 Survey Paper on Graph Coloring Problem and Its Application

Authors: Prateek Chharia, Biswa Bhusan Ghosh


Graph coloring is one of the prominent concepts in graph coloring. It can be defined as a coloring of the various regions of the graph such that all the constraints are fulfilled. In this paper various graphs coloring approaches like greedy coloring, Heuristic search for maximum independent set and graph coloring using edge table is described. Graph coloring can be used in various real time applications like student time tabling generation, Sudoku as a graph coloring problem, GSM phone network.

Keywords: graph coloring, greedy coloring, heuristic search, edge table, sudoku as a graph coloring problem

Procedia PDF Downloads 435
1541 A New Graph Theoretic Problem with Ample Practical Applications

Authors: Mehmet Hakan Karaata


In this paper, we first coin a new graph theocratic problem with numerous applications. Second, we provide two algorithms for the problem. The first solution is using a brute-force techniques, whereas the second solution is based on an initial identification of the cycles in the given graph. We then provide a correctness proof of the algorithm. The applications of the problem include graph analysis, graph drawing and network structuring.

Keywords: algorithm, cycle, graph algorithm, graph theory, network structuring

Procedia PDF Downloads 273
1540 Complete Tripartite Graphs with Spanning Maximal Planar Subgraphs

Authors: Severino Gervacio, Velimor Almonte, Emmanuel Natalio


A simple graph is planar if it there is a way of drawing it in the plane without edge crossings. A planar graph which is not a proper spanning subgraph of another planar graph is a maximal planar graph. We prove that for complete tripartite graphs of order at most 9, the only ones that contain a spanning maximal planar subgraph are K1,1,1, K2,2,2, K2,3,3, and K3,3,3. The main result gives a necessary and sufficient condition for the complete tripartite graph Kx,y,z to contain a spanning maximal planar subgraph.

Keywords: complete tripartite graph, graph, maximal planar graph, planar graph, subgraph

Procedia PDF Downloads 235
1539 Efficient Filtering of Graph Based Data Using Graph Partitioning

Authors: Nileshkumar Vaishnav, Aditya Tatu


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.

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

Procedia PDF Downloads 225
1538 Improvement a Lower Bound of Energy for Some Family of Graphs, Related to Determinant of Adjacency Matrix

Authors: Saieed Akbari, Yousef Bagheri, Amir Hossein Ghodrati, Sima Saadat Akhtar


Let G be a simple graph with the vertex set V (G) and with the adjacency matrix A (G). The energy E (G) of G is defined to be the sum of the absolute values of all eigenvalues of A (G). Also let n and m be number of edges and vertices of the graph respectively. A regular graph is a graph where each vertex has the same number of neighbours. Given a graph G, its line graph L(G) is a graph such that each vertex of L(G) represents an edge of G; and two vertices of L(G) are adjacent if and only if their corresponding edges share a common endpoint in G. In this paper we show that for every regular graphs and also for every line graphs such that (G) 3 we have, E(G) 2nm + n 1. Also at the other part of the paper we prove that 2 (G) E(G) for an arbitrary graph G.

Keywords: eigenvalues, energy, line graphs, matching number

Procedia PDF Downloads 107
1537 Graph Similarity: Algebraic Model and Its Application to Nonuniform Signal Processing

Authors: Nileshkumar Vishnav, Aditya Tatu


A recent approach of representing graph signals and graph filters as polynomials is useful for graph signal processing. In this approach, the adjacency matrix plays pivotal role; instead of the more common approach involving graph-Laplacian. In this work, we follow the adjacency matrix based approach and corresponding algebraic signal model. We further expand the theory and introduce the concept of similarity of two graphs. The similarity of graphs is useful in that key properties (such as filter-response, algebra related to graph) get transferred from one graph to another. We demonstrate potential applications of the relation between two similar graphs, such as nonuniform filter design, DTMF detection and signal reconstruction.

Keywords: graph signal processing, algebraic signal processing, graph similarity, isospectral graphs, nonuniform signal processing

Procedia PDF Downloads 258
1536 Metric Dimension on Line Graph of Honeycomb Networks

Authors: M. Hussain, Aqsa Farooq


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.

Keywords: Resolving set, Metric dimension, Honeycomb network, Line graph

Procedia PDF Downloads 81
1535 Speedup Breadth-First Search by Graph Ordering

Authors: Qiuyi Lyu, Bin Gong


Breadth-First Search(BFS) is a core graph algorithm that is widely used for graph analysis. As it is frequently used in many graph applications, improve the BFS performance is essential. In this paper, we present a graph ordering method that could reorder the graph nodes to achieve better data locality, thus, improving the BFS performance. Our method is based on an observation that the sibling relationships will dominate the cache access pattern during the BFS traversal. Therefore, we propose a frequency-based model to construct the graph order. First, we optimize the graph order according to the nodes’ visit frequency. Nodes with high visit frequency will be processed in priority. Second, we try to maximize the child nodes overlap layer by layer. As it is proved to be NP-hard, we propose a heuristic method that could greatly reduce the preprocessing overheads. We conduct extensive experiments on 16 real-world datasets. The result shows that our method could achieve comparable performance with the state-of-the-art methods while the graph ordering overheads are only about 1/15.

Keywords: breadth-first search, BFS, graph ordering, graph algorithm

Procedia PDF Downloads 51
1534 On the Zeros of the Degree Polynomial of a Graph

Authors: S. R. Nayaka, Putta Swamy


Graph polynomial is one of the algebraic representations of the Graph. The degree polynomial is one of the simple algebraic representations of graphs. The degree polynomial of a graph G of order n is the polynomial Deg(G, x) with the coefficients deg(G,i) where deg(G,i) denotes the number of vertices of degree i in G. In this article, we investigate the behavior of the roots of some families of Graphs in the complex field. We investigate for the graphs having only integral roots. Further, we characterize the graphs having single roots or having real roots and behavior of the polynomial at the particular value is also obtained.

Keywords: degree polynomial, regular graph, minimum and maximum degree, graph operations

Procedia PDF Downloads 153
1533 From Convexity in Graphs to Polynomial Rings

Authors: Ladznar S. Laja, Rosalio G. Artes, Jr.


This paper introduced a graph polynomial relating convexity concepts. A graph polynomial is a polynomial representing a graph given some parameters. On the other hand, a subgraph H of a graph G is said to be convex in G if for every pair of vertices in H, every shortest path with these end-vertices lies entirely in H. We define the convex subgraph polynomial of a graph G to be the generating function of the sequence of the numbers of convex subgraphs of G of cardinalities ranging from zero to the order of G. This graph polynomial is monic since G itself is convex. The convex index which counts the number of convex subgraphs of G of all orders is just the evaluation of this polynomial at 1. Relationships relating algebraic properties of convex subgraphs polynomial with graph theoretic concepts are established.

Keywords: convex subgraph, convex index, generating function, polynomial ring

Procedia PDF Downloads 125
1532 An Application of Graph Theory to The Electrical Circuit Using Matrix Method

Authors: Samai'la Abdullahi


A graph is a pair of two set and so that a graph is a pictorial representation of a system using two basic element nodes and edges. A node is represented by a circle (either hallo shade) and edge is represented by a line segment connecting two nodes together. In this paper, we present a circuit network in the concept of graph theory application and also circuit models of graph are represented in logical connection method were we formulate matrix method of adjacency and incidence of matrix and application of truth table.

Keywords: euler circuit and path, graph representation of circuit networks, representation of graph models, representation of circuit network using logical truth table

Procedia PDF Downloads 467
1531 Building 1-Well-Covered Graphs by Corona, Join, and Rooted Product of Graphs

Authors: Vadim E. Levit, Eugen Mandrescu


A graph is well-covered if all its maximal independent sets are of the same size. A well-covered graph is 1-well-covered if deletion of every vertex of the graph leaves it well-covered. It is known that a graph without isolated vertices is 1-well-covered if and only if every two disjoint independent sets are included in two disjoint maximum independent sets. Well-covered graphs are related to combinatorial commutative algebra (e.g., every Cohen-Macaulay graph is well-covered, while each Gorenstein graph without isolated vertices is 1-well-covered). Our intent is to construct several infinite families of 1-well-covered graphs using the following known graph operations: corona, join, and rooted product of graphs. Adopting some known techniques used to advantage for well-covered graphs, one can prove that: if the graph G has no isolated vertices, then the corona of G and H is 1-well-covered if and only if H is a complete graph of order two at least; the join of the graphs G and H is 1-well-covered if and only if G and H have the same independence number and both are 1-well-covered; if H satisfies the property that every three pairwise disjoint independent sets are included in three pairwise disjoint maximum independent sets, then the rooted product of G and H is 1-well-covered, for every graph G. These findings show not only how to generate some more families of 1-well-covered graphs, but also that, to this aim, sometimes, one may use graphs that are not necessarily 1-well-covered.

Keywords: maximum independent set, corona, concatenation, join, well-covered graph

Procedia PDF Downloads 99
1530 Nullity of t-Tupple Graphs

Authors: Khidir R. Sharaf, Didar A. Ali


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 sub-graph 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 end vertex 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, statistic

Procedia PDF Downloads 150
1529 Existence and Construction of Maximal Rectangular Duals

Authors: Krishnendra Shekhawat


Given a graph G = (V, E), a rectangular dual of G represents the vertices of G by a set of interior-disjoint rectangles such that two rectangles touch if and only if there is an edge between the two corresponding vertices in G. Rectangular duals do not exist for every graph, so we can define maximal rectangular duals. A maximal rectangular dual is a rectangular dual of a graph G such that there exists no graph G ′ with a rectangular dual where G is a subgraph of G ′. In this paper, we enumerate all maximal rectangular duals (or, to be precise, the corresponding planar graphs) up to six nodes and presents a necessary condition for the existence of a rectangular dual. This work allegedly has applications in integrated circuit design and architectural floor plans.

Keywords: adjacency, degree sequence, dual graph, rectangular dual

Procedia PDF Downloads 141
1528 Characterising Stable Model by Extended Labelled Dependency Graph

Authors: Asraful Islam


Extended dependency graph (EDG) is a state-of-the-art isomorphic graph to represent normal logic programs (NLPs) that can characterize the consistency of NLPs by graph analysis. To construct the vertices and arcs of an EDG, additional renaming atoms and rules besides those the given program provides are used, resulting in higher space complexity compared to the corresponding traditional dependency graph (TDG). In this article, we propose an extended labeled dependency graph (ELDG) to represent an NLP that shares an equal number of nodes and arcs with TDG and prove that it is isomorphic to the domain program. The number of nodes and arcs used in the underlying dependency graphs are formulated to compare the space complexity. Results show that ELDG uses less memory to store nodes, arcs, and cycles compared to EDG. To exhibit the desirability of ELDG, firstly, the stable models of the kernel form of NLP are characterized by the admissible coloring of ELDG; secondly, a relation of the stable models of a kernel program with the handles of the minimal, odd cycles appearing in the corresponding ELDG has been established; thirdly, to our best knowledge, for the first time an inverse transformation from a dependency graph to the representing NLP w.r.t. ELDG has been defined that enables transferring analytical results from the graph to the program straightforwardly.

Keywords: normal logic program, isomorphism of graph, extended labelled dependency graph, inverse graph transforma-tion, graph colouring

Procedia PDF Downloads 119
1527 Introduction to Paired Domination Polynomial of a Graph

Authors: Puttaswamy, Anwar Alwardi, Nayaka S. R.


One of the algebraic representation of a graph is the graph polynomial. In this article, we introduce the paired-domination polynomial of a graph G. The paired-domination polynomial of a graph G of order n is the polynomial Dp(G, x) with the coefficients dp(G, i) where dp(G, i) denotes the number of paired dominating sets of G of cardinality i and γpd(G) denotes the paired-domination number of G. We obtain some properties of Dp(G, x) and its coefficients. Further, we compute this polynomial for some families of standard graphs. Further, we obtain some characterization for some specific graphs.

Keywords: domination polynomial, paired dominating set, paired domination number, paired domination polynomial

Procedia PDF Downloads 148
1526 Eccentric Connectivity Index, First and Second Zagreb Indices of Corona Graph

Authors: A. Kulandai Therese


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 division-related corona graphs.

Keywords: corona graph, degree, eccentricity, eccentric connectivity index, first zagreb index, second zagreb index, subdivision graphs

Procedia PDF Downloads 243
1525 2D Structured Non-Cyclic Fuzzy Graphs

Authors: T. Pathinathan, M. Peter


Fuzzy graphs incorporate concepts from graph theory with fuzzy principles. In this paper, we make a study on the properties of fuzzy graphs which are non-cyclic and are of two-dimensional in structure. In particular, this paper presents 2D structure or the structure of double layer for a non-cyclic fuzzy graph whose underlying crisp graph is non-cyclic. In any graph structure, introducing 2D structure may lead to an inherent cycle. We propose relevant conditions for 2D structured non-cyclic fuzzy graphs. These conditions are extended even to fuzzy graphs of the 3D structure. General theoretical properties that are studied for any fuzzy graph are verified to 2D structured or double layered fuzzy graphs. Concepts like Order, Degree, Strong and Size for a fuzzy graph are studied for 2D structured or double layered non-cyclic fuzzy graphs. Using different types of fuzzy graphs, the proposed concepts relating to 2D structured fuzzy graphs are verified.

Keywords: double layered fuzzy graph, double layered non–cyclic fuzzy graph, order, degree and size

Procedia PDF Downloads 279
1524 Aerodynamic Investigation of Baseline-IV Bird-Inspired BWB Aircraft Design: Improvements over Baseline-III BWB

Authors: C. M. Nur Syazwani, M. K. Ahmad Imran, Rizal E. M. Nasir


The study on BWB UV begins in UiTM since 2005 and three designs have been studied and published. The latest designs are Baseline-III and inspired by birds that have features and aerodynamics behaviour of cruising birds without flapping capability. The aircraft featuring planform and configuration are similar to the bird. Baseline-III has major flaws particularly in its low lift-to-drag ratio, stability and issues regarding limited controllability. New design known as Baseline-IV replaces straight, swept wing to delta wing and have a broader tail compares to the Baseline-III’s. The objective of the study is to investigate aerodynamics of Baseline-IV bird-inspired BWB aircraft. This will be achieved by theoretical calculation and wind tunnel experiments. The result shows that both theoretical and wind tunnel experiments of Baseline-IV graph of CL and CD versus alpha are quite similar to each other in term of pattern of graph slopes and values. Baseline-IV has higher lift coefficient values at wide range of angle of attack compares to Baseline-III. Baseline-IV also has higher maximum lift coefficient, higher maximum lift-to-drag and lower parasite drag. It has stable pitch moment versus lift slope but negative moment at zero lift for zero angle-of-attack tail setting. At high angle of attack, Baseline-IV does not have stability reversal as shown in Baseline-III. Baseline-IV is proven to have improvements over Baseline-III in terms of lift, lift-to-drag ratio and pitch moment stability at high angle-of-attack.

Keywords: blended wing-body, bird-inspired blended wing-body, aerodynamic, stability

Procedia PDF Downloads 439
1523 Multi-Stream Graph Attention Network for Recommendation with Knowledge Graph

Authors: Zhifei Hu, Feng Xia


In recent years, Graph neural network has been widely used in knowledge graph recommendation. The existing recommendation methods based on graph neural network extract information from knowledge graph through entity and relation, which may not be efficient in the way of information extraction. In order to better propose useful entity information for the current recommendation task in the knowledge graph, we propose an end-to-end Neural network Model based on multi-stream graph attentional Mechanism (MSGAT), which can effectively integrate the knowledge graph into the recommendation system by evaluating the importance of entities from both users and items. Specifically, we use the attention mechanism from the user's perspective to distil the domain nodes information of the predicted item in the knowledge graph, to enhance the user's information on items, and generate the feature representation of the predicted item. Due to user history, click items can reflect the user's interest distribution, we propose a multi-stream attention mechanism, based on the user's preference for entities and relationships, and the similarity between items to be predicted and entities, aggregate user history click item's neighborhood entity information in the knowledge graph and generate the user's feature representation. We evaluate our model on three real recommendation datasets: Movielens-1M (ML-1M), LFM-1B 2015 (LFM-1B), and Amazon-Book (AZ-book). Experimental results show that compared with the most advanced models, our proposed model can better capture the entity information in the knowledge graph, which proves the validity and accuracy of the model.

Keywords: graph attention network, knowledge graph, recommendation, information propagation

Procedia PDF Downloads 15
1522 Bounds on the Laplacian Vertex PI Energy

Authors: Ezgi Kaya, A. Dilek Maden


A topological index is a number related to graph which is invariant under graph isomorphism. In theoretical chemistry, molecular structure descriptors (also called topological indices) are used for modeling physicochemical, pharmacologic, toxicologic, biological and other properties of chemical compounds. Let G be a graph with n vertices and m edges. For a given edge uv, the quantity nu(e) denotes the number of vertices closer to u than v, the quantity nv(e) is defined analogously. The vertex PI index defined as the sum of the nu(e) and nv(e). Here the sum is taken over all edges of G. The energy of a graph is defined as the sum of the eigenvalues of adjacency matrix of G and the Laplacian energy of a graph is defined as the sum of the absolute value of difference of laplacian eigenvalues and average degree of G. In theoretical chemistry, the π-electron energy of a conjugated carbon molecule, computed using the Hückel theory, coincides with the energy. Hence results on graph energy assume special significance. The Laplacian matrix of a graph G weighted by the vertex PI weighting is the Laplacian vertex PI matrix and the Laplacian vertex PI eigenvalues of a connected graph G are the eigenvalues of its Laplacian vertex PI matrix. In this study, Laplacian vertex PI energy of a graph is defined of G. We also give some bounds for the Laplacian vertex PI energy of graphs in terms of vertex PI index, the sum of the squares of entries in the Laplacian vertex PI matrix and the absolute value of the determinant of the Laplacian vertex PI matrix.

Keywords: energy, Laplacian energy, laplacian vertex PI eigenvalues, Laplacian vertex PI energy, vertex PI index

Procedia PDF Downloads 154
1521 Graph Codes - 2D Projections of Multimedia Feature Graphs for Fast and Effective Retrieval

Authors: Stefan Wagenpfeil, Felix Engel, Paul McKevitt, Matthias Hemmje


Multimedia Indexing and Retrieval is generally designed and implemented by employing feature graphs. These graphs typically contain a significant number of nodes and edges to reflect the level of detail in feature detection. A higher level of detail increases the effectiveness of the results but also leads to more complex graph structures. However, graph-traversal-based algorithms for similarity are quite inefficient and computation intensive, especially for large data structures. To deliver fast and effective retrieval, an efficient similarity algorithm, particularly for large graphs, is mandatory. Hence, in this paper, we define a graph-projection into a 2D space (Graph Code) as well as the corresponding algorithms for indexing and retrieval. We show that calculations in this space can be performed more efficiently than graph-traversals due to a simpler processing model and a high level of parallelization. In consequence, we prove that the effectiveness of retrieval also increases substantially, as Graph Codes facilitate more levels of detail in feature fusion. Thus, Graph Codes provide a significant increase in efficiency and effectiveness (especially for Multimedia indexing and retrieval) and can be applied to images, videos, audio, and text information.

Keywords: indexing, retrieval, multimedia, graph algorithm, graph code

Procedia PDF Downloads 64
1520 Construction of Graph Signal Modulations via Graph Fourier Transform and Its Applications

Authors: Xianwei Zheng, Yuan Yan Tang


Classical window Fourier transform has been widely used in signal processing, image processing, machine learning and pattern recognition. The related Gabor transform is powerful enough to capture the texture information of any given dataset. Recently, in the emerging field of graph signal processing, researchers devoting themselves to develop a graph signal processing theory to handle the so-called graph signals. Among the new developing theory, windowed graph Fourier transform has been constructed to establish a time-frequency analysis framework of graph signals. The windowed graph Fourier transform is defined by using the translation and modulation operators of graph signals, following the similar calculations in classical windowed Fourier transform. Specifically, the translation and modulation operators of graph signals are defined by using the Laplacian eigenvectors as follows. For a given graph signal, its translation is defined by a similar manner as its definition in classical signal processing. Specifically, the translation operator can be defined by using the Fourier atoms; the graph signal translation is defined similarly by using the Laplacian eigenvectors. The modulation of the graph can also be established by using the Laplacian eigenvectors. The windowed graph Fourier transform based on these two operators has been applied to obtain time-frequency representations of graph signals. Fundamentally, the modulation operator is defined similarly to the classical modulation by multiplying a graph signal with the entries in each Fourier atom. However, a single Laplacian eigenvector entry cannot play a similar role as the Fourier atom. This definition ignored the relationship between the translation and modulation operators. In this paper, a new definition of the modulation operator is proposed and thus another time-frequency framework for graph signal is constructed. Specifically, the relationship between the translation and modulation operations can be established by the Fourier transform. Specifically, for any signal, the Fourier transform of its translation is the modulation of its Fourier transform. Thus, the modulation of any signal can be defined as the inverse Fourier transform of the translation of its Fourier transform. Therefore, similarly, the graph modulation of any graph signal can be defined as the inverse graph Fourier transform of the translation of its graph Fourier. The novel definition of the graph modulation operator established a relationship of the translation and modulation operations. The new modulation operation and the original translation operation are applied to construct a new framework of graph signal time-frequency analysis. Furthermore, a windowed graph Fourier frame theory is developed. Necessary and sufficient conditions for constructing windowed graph Fourier frames, tight frames and dual frames are presented in this paper. The novel graph signal time-frequency analysis framework is applied to signals defined on well-known graphs, e.g. Minnesota road graph and random graphs. Experimental results show that the novel framework captures new features of graph signals.

Keywords: graph signals, windowed graph Fourier transform, windowed graph Fourier frames, vertex frequency analysis

Procedia PDF Downloads 251
1519 On Chromaticity of Wheels

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


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

Procedia PDF Downloads 334
1518 Hybrid Approximate Structural-Semantic Frequent Subgraph Mining

Authors: Montaceur Zaghdoud, Mohamed Moussaoui, Jalel Akaichi


Frequent subgraph mining refers usually to graph matching and it is widely used in when analyzing big data with large graphs. A lot of research works dealt with structural exact or inexact graph matching but a little attention is paid to semantic matching when graph vertices and/or edges are attributed and typed. Therefore, it seems very interesting to integrate background knowledge into the analysis and that extracted frequent subgraphs should become more pruned by applying a new semantic filter instead of using only structural similarity in graph matching process. Consequently, this paper focuses on developing a new hybrid approximate structuralsemantic graph matching to discover a set of frequent subgraphs. It uses simultaneously an approximate structural similarity function based on graph edit distance function and a possibilistic vertices similarity function based on affinity function. Both structural and semantic filters contribute together to prune extracted frequent set. Indeed, new hybrid structural-semantic frequent subgraph mining approach searches will be suitable to be applied to several application such as community detection in social networks.

Keywords: approximate graph matching, hybrid frequent subgraph mining, graph mining, possibility theory

Procedia PDF Downloads 312
1517 A Study of Chromatic Uniqueness of W14

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


Coloring 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 W14 is chromatically unique.

Keywords: chromatic polynomial, chromatically Equivalent, chromatically unique, wheel

Procedia PDF Downloads 328
1516 The K-Distance Neighborhood Polynomial of a Graph

Authors: Soner Nandappa D., Ahmed Mohammed Naji


In a graph G = (V, E), the distance from a vertex v to a vertex u is the length of shortest v to u path. The eccentricity e(v) of v is the distance to a farthest vertex from v. The diameter diam(G) is the maximum eccentricity. The k-distance neighborhood of v, for 0 ≤ k ≤ e(v), is Nk(v) = {u ϵ V (G) : d(v, u) = k}. In this paper, we introduce a new distance degree based topological polynomial of a graph G is called a k- distance neighborhood polynomial, denoted Nk(G, x). It is a polynomial with the coefficient of the term k, for 0 ≤ k ≤ e(v), is the sum of the cardinalities of Nk(v) for every v ϵ V (G). Some properties of k- distance neighborhood polynomials are obtained. Exact formulas of the k- distance neighborhood polynomial for some well-known graphs, Cartesian product and join of graphs are presented.

Keywords: vertex degrees, distance in graphs, graph operation, Nk-polynomials

Procedia PDF Downloads 323
1515 A Graph Library Development Based on the Service-‎Oriented Architecture: Used for Representation of the ‎Biological ‎Systems in the Computer Algorithms

Authors: Mehrshad Khosraviani, Sepehr Najjarpour


Considering the usage of graph-based approaches in systems and synthetic biology, and the various types of ‎the graphs employed by them, a comprehensive graph library based ‎on the three-tier architecture (3TA) was previously introduced for full representation of the biological systems. Although proposing a 3TA-based graph library, three following reasons motivated us to redesign the graph ‎library based on the service-oriented architecture (SOA): (1) Maintaining the accuracy of the data related to an input graph (including its edges, its ‎vertices, its topology, etc.) without involving the end user:‎ Since, in the case of using 3TA, the library files are available to the end users, they may ‎be utilized incorrectly, and consequently, the invalid graph data will be provided to the ‎computer algorithms. However, considering the usage of the SOA, the operation of the ‎graph registration is specified as a service by encapsulation of the library files. In other words, overall control operations needed for registration of the valid data will be the ‎responsibility of the services. (2) Partitioning of the library product into some different parts: Considering 3TA, a whole library product was provided in general. While here, the product ‎can be divided into smaller ones, such as an AND/OR graph drawing service, and each ‎one can be provided individually. As a result, the end user will be able to select any ‎parts of the library product, instead of all features, to add it to a project. (3) Reduction of the complexities: While using 3TA, several other libraries must be needed to add for connecting to the ‎database, responsibility of the provision of the needed library resources in the SOA-‎based graph library is entrusted with the services by themselves. Therefore, the end user ‎who wants to use the graph library is not involved with its complexity. In the end, in order to ‎make ‎the library easier to control in the system, and to restrict the end user from accessing the files, ‎it was preferred to use the service-oriented ‎architecture ‎‎(SOA) over the three-tier architecture (3TA) and to redevelop the previously proposed graph library based on it‎.

Keywords: Bio-Design Automation, Biological System, Graph Library, Service-Oriented Architecture, Systems and Synthetic Biology

Procedia PDF Downloads 115
1514 Normalized Laplacian Eigenvalues of Graphs

Authors: Shaowei Sun


Let G be a graph with vertex set V(G)={v_1,v_2,...,v_n} and edge set E(G). For any vertex v belong to V(G), let d_v denote the degree of v. The normalized Laplacian matrix of the graph G is the matrix where the non-diagonal (i,j)-th entry is -1/(d_id_j) when vertex i is adjacent to vertex j and 0 when they are not adjacent, and the diagonal (i,i)-th entry is the di. In this paper, we discuss some bounds on the largest and the second smallest normalized Laplacian eigenvalue of trees and graphs. As following, we found some new bounds on the second smallest normalized Laplacian eigenvalue of tree T in terms of graph parameters. Moreover, we use Sage to give some conjectures on the second largest and the third smallest normalized eigenvalues of graph.

Keywords: graph, normalized Laplacian eigenvalues, normalized Laplacian matrix, tree

Procedia PDF Downloads 246