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

Search results for: vertex enumeration

102 Exploring Counting Methods for the Vertices of Certain Polyhedra with Uncertainties

Authors: Sammani Danwawu Abdullahi

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.

Keywords: counting with uncertainties, mathematical programming, optimization, vertex enumeration

Procedia PDF Downloads 267
101 The Vertex Degree Distance of One Vertex Union of the Cycle and the Star

Authors: Ying Wang, Haiyan Xie, Aoming Zhang

Abstract:

The degree distance of a graph is a graph invariant that is more sensitive than the Wiener index. In this paper, we calculate the vertex degree distances of one vertex union of the cycle and the star, and the degree distance of one vertex union of the cycle and the star. These results lay a foundation for further study on the extreme value of the vertex degree distances, and the distribution of the vertices with the extreme value in one vertex union of the cycle and the star.

Keywords: degree distance, vertex-degree-distance, one vertex union of a cycle and a star, graph

Procedia PDF Downloads 64
100 Bounds on the Laplacian Vertex PI Energy

Authors: Ezgi Kaya, A. Dilek Maden

Abstract:

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 155
99 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 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 152
98 The K-Distance Neighborhood Polynomial of a Graph

Authors: Soner Nandappa D., Ahmed Mohammed Naji

Abstract:

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 327
97 Normalized Laplacian Eigenvalues of Graphs

Authors: Shaowei Sun

Abstract:

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
96 GPU-Accelerated Triangle Mesh Simplification Using Parallel Vertex Removal

Authors: Thomas Odaker, Dieter Kranzlmueller, Jens Volkert

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.

Keywords: computer graphics, half edge collapse, mesh simplification, precomputed simplification, topology preserving

Procedia PDF Downloads 274
95 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

Abstract:

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 113
94 Passive Control of Elliptic Jet by Using Triangular and Truncated Tabs

Authors: Saif Akram, E. Rathakrishnan

Abstract:

The mixing promoting efficiency of two identical sharp and truncated vertex triangular tabs offering geometrical blockage of 2.5% each, placed at the exit of a Mach 1.5 elliptic nozzle was studied experimentally. The effectiveness of both the tabs in enhancing the mixing of jets with the ambient air are determined by measuring the Pitot pressure along the jet axis and the jet spread in both the minor and major axes of the elliptic nozzle, covering marginally overexpanded to moderately underexpanded levels at the nozzle exit. The results reveal that both the tabs enhance mixing characteristics of the uncontrolled elliptic jet when placed at minor axis. A core length reduction of 67% is achieved at NPR 3 which is the overexpanded state. Similarly, the core length is reduced by about 67%, 50% and 57% at NPRs of 4, 5 and 6 (underexpanded states) respectively. However, unlike the considerable increment in mixing promoting efficiency by the use of truncated vertex tabs for axisymmetric jets, the effect is not much pronounced for the case of supersonic elliptic jets. The CPD plots for both the cases almost overlap, especially when tabs are placed at minor axis, at all the pressure conditions. While, when the tabs are used at major axis, in the case of overexpanded condition, the sharp vertex triangular tabs act as a better mixing enhancer for the supersonic elliptic jets. For the jet controlled with truncated vertex triangular tabs, the core length reductions are of the same order as those for the sharp vertex triangular tabs. The jet mixing is hardly influenced by the tip effect in case of supersonic elliptic jet.

Keywords: elliptic jet, tabs, truncated, triangular

Procedia PDF Downloads 314
93 Undirected Endo-Cayley Digraphs of Cyclic Groups of Order Primes

Authors: Chanon Promsakon, Sayan Panma

Abstract:

Let S be a finite semigroup, A a subset of S and f an endomorphism on S. The endo-Cayley digraph of a semigroup S corresponding to a connecting set A and an endomorphism f, denoted by endo − Cayf (S, A) is a digraph whose vertex set is S and a vertex u is adjacent to a vertex v if and only if v = f(u)a for some a ∈ A. A digraph D is called undirected if any edge uv in D, there exists an edge vu in D. We consider the undirectedness of an endo-Cayley of a cyclic group of order prime, Zp. In this work, we investigate conditions for connecting sets and endomorphisms to make endo-Cayley digraphs of cyclic groups of order primes be undirected. Moreover, we give some conditions for an undirected endo-Cayley of cycle group of any order.

Keywords: endo-Cayley graph, undirected digraphs, cyclic groups, endomorphism

Procedia PDF Downloads 226
92 Identifying Coloring in Graphs with Twins

Authors: Souad Slimani, Sylvain Gravier, Simon Schmidt

Abstract:

Recently, several vertex identifying notions were introduced (identifying coloring, lid-coloring,...); these notions were inspired by identifying codes. All of them, as well as original identifying code, is based on separating two vertices according to some conditions on their closed neighborhood. Therefore, twins can not be identified. So most of known results focus on twin-free graph. Here, we show how twins can modify optimal value of vertex-identifying parameters for identifying coloring and locally identifying coloring.

Keywords: identifying coloring, locally identifying coloring, twins, separating

Procedia PDF Downloads 61
91 Multiple-Channel Coulter Counter for Cell Sizing and Enumeration

Authors: Yu Chen, Seong-Jin Kim, Jaehoon Chung

Abstract:

High throughput cells counting and sizing are often required for biomedical applications. Here we report design, fabrication and validating of a micro-machined Coulter counter device with multiple-channel to realize such application for low cost. Multiple vertical through-holes were fabricated on a silicon chip, combined with the PDMS micro-fluidics channel that serves as the sensing channel. In order to avoid the crosstalk introduced by the electrical connection, instead of measuring the current passing through, the potential of each channel is monitored, thus the high throughput is possible. A peak of the output potential can be captured when the cell/particle is passing through the microhole. The device was validated by counting and sizing the polystyrene beads with diameter of 6 μm, 10 μm and 15 μm. With the sampling frequency to be set at 100 kHz, up to 5000 counts/sec for each channel can be realized. The counting and enumeration of MCF7 cancer cells are also demonstrated.

Keywords: Coulter counter, cell enumeration, high through-put, cell sizing

Procedia PDF Downloads 499
90 Comparative Study of Skeletonization and Radial Distance Methods for Automated Finger Enumeration

Authors: Mohammad Hossain Mohammadi, Saif Al Ameri, Sana Ziaei, Jinane Mounsef

Abstract:

Automated enumeration of the number of hand fingers is widely used in several motion gaming and distance control applications, and is discussed in several published papers as a starting block for hand recognition systems. The automated finger enumeration technique should not only be accurate, but also must have a fast response for a moving-picture input. The high performance of video in motion games or distance control will inhibit the program’s overall speed, for image processing software such as Matlab need to produce results at high computation speeds. Since an automated finger enumeration with minimum error and processing time is desired, a comparative study between two finger enumeration techniques is presented and analyzed in this paper. In the pre-processing stage, various image processing functions were applied on a real-time video input to obtain the final cleaned auto-cropped image of the hand to be used for the two techniques. The first technique uses the known morphological tool of skeletonization to count the number of skeleton’s endpoints for fingers. The second technique uses a radial distance method to enumerate the number of fingers in order to obtain a one dimensional hand representation. For both discussed methods, the different steps of the algorithms are explained. Then, a comparative study analyzes the accuracy and speed of both techniques. Through experimental testing in different background conditions, it was observed that the radial distance method was more accurate and responsive to a real-time video input compared to the skeletonization method. All test results were generated in Matlab and were based on displaying a human hand for three different orientations on top of a plain color background. Finally, the limitations surrounding the enumeration techniques are presented.

Keywords: comparative study, hand recognition, fingertip detection, skeletonization, radial distance, Matlab

Procedia PDF Downloads 300
89 Total Chromatic Number of Δ-Claw-Free 3-Degenerated Graphs

Authors: Wongsakorn Charoenpanitseri

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.

Keywords: total colorings, the total chromatic number, 3-degenerated, CLAW-FREE

Procedia PDF Downloads 109
88 Deciding Graph Non-Hamiltonicity via a Closure Algorithm

Authors: E. R. Swart, S. J. Gismondi, N. R. Swart, C. E. Bell

Abstract:

We present an heuristic algorithm that decides graph non-Hamiltonicity. All graphs are directed, each undirected edge regarded as a pair of counter directed arcs. Each of the n! Hamilton cycles in a complete graph on n+1 vertices is mapped to an n-permutation matrix P where p(u,i)=1 if and only if the ith arc in a cycle enters vertex u, starting and ending at vertex n+1. We first create exclusion set E by noting all arcs (u, v) not in G, sufficient to code precisely all cycles excluded from G i.e. cycles not in G use at least one arc not in G. Members are pairs of components of P, {p(u,i),p(v,i+1)}, i=1, n-1. A doubly stochastic-like relaxed LP formulation of the Hamilton cycle decision problem is constructed. Each {p(u,i),p(v,i+1)} in E is coded as variable q(u,i,v,i+1)=0 i.e. shrinks the feasible region. We then implement the Weak Closure Algorithm (WCA) that tests necessary conditions of a matching, together with Boolean closure to decide 0/1 variable assignments. Each {p(u,i),p(v,j)} not in E is tested for membership in E, and if possible, added to E (q(u,i,v,j)=0) to iteratively maximize |E|. If the WCA constructs E to be maximal, the set of all {p(u,i),p(v,j)}, then G is decided non-Hamiltonian. Only non-Hamiltonian G share this maximal property. Ten non-Hamiltonian graphs (10 through 104 vertices) and 2000 randomized 31 vertex non-Hamiltonian graphs are tested and correctly decided non-Hamiltonian. For Hamiltonian G, the complement of E covers a matching, perhaps useful in searching for cycles. We also present an example where the WCA fails.

Keywords: Hamilton cycle decision problem, computational complexity theory, graph theory, theoretical computer science

Procedia PDF Downloads 292
87 Comparison of Automated Zone Design Census Output Areas with Existing Output Areas in South Africa

Authors: T. Mokhele, O. Mutanga, F. Ahmed

Abstract:

South Africa is one of the few countries that have stopped using the same Enumeration Areas (EAs) for census enumeration and dissemination. The advantage of this change is that confidentiality issue could be addressed for census dissemination as the design of geographic unit for collection is mainly to ensure that this unit is covered by one enumerator. The objective of this paper was to evaluate the performance of automated zone design output areas against non-zone design developed geographies using the 2001 census data, and 2011 census to some extent, as the main input. The comparison of the Automated Zone-design Tool (AZTool) census output areas with the Small Area Layers (SALs) and SubPlaces based on confidentiality limit, population distribution, and degree of homogeneity, as well as shape compactness, was undertaken. Further, SPSS was employed for validation of the AZTool output results. The results showed that AZTool developed output areas out-perform the existing official SAL and SubPlaces with regard to minimum population threshold, population distribution and to some extent to homogeneity. Therefore, it was concluded that AZTool program provides a new alternative to the creation of optimised census output areas for dissemination of population census data in South Africa.

Keywords: AZTool, enumeration areas, small areal layers, South Africa

Procedia PDF Downloads 116
86 Location-Domination on Join of Two Graphs and Their Complements

Authors: Analen Malnegro, Gina Malacas

Abstract:

Dominating sets and related topics have been studied extensively in the past few decades. A dominating set of a graph G is a subset D of V such that every vertex not in D is adjacent to at least one member of D. The domination number γ(G) is the number of vertices in a smallest dominating set for G. Some problems involving detection devices can be modeled with graphs. Finding the minimum number of devices needed according to the type of devices and the necessity of locating the object gives rise to locating-dominating sets. A subset S of vertices of a graph G is called locating-dominating set, LD-set for short, if it is a dominating set and if every vertex v not in S is uniquely determined by the set of neighbors of v belonging to S. The location-domination number λ(G) is the minimum cardinality of an LD-set for G. The complement of a graph G is a graph Ḡ on same vertices such that two distinct vertices of Ḡ are adjacent if and only if they are not adjacent in G. An LD-set of a graph G is global if it is an LD-set of both G and its complement Ḡ. The global location-domination number λg(G) is defined as the minimum cardinality of a global LD-set of G. In this paper, global LD-sets on the join of two graphs are characterized. Global location-domination numbers of these graphs are also determined.

Keywords: dominating set, global locating-dominating set, global location-domination number, locating-dominating set, location-domination number

Procedia PDF Downloads 108
85 Independence and Path Independence on Cayley Digraphs of Left Groups and Right Groups

Authors: Nuttawoot Nupo, Sayan Panma

Abstract:

A semigroup S is said to be a left (right) zero semigroup if S satisfies the equation xy=x (xy=y) for all x,y in S. In addition, the semigroup S is called a left (right) group if S is isomorphic to the direct product of a group and a left (right) zero semigroup. The Cayley digraph Cay(S,A) of a semigroup S with a connection set A is defined to be a digraph with the vertex set S and the arc set E(Cay(S,A))={(x,xa) | x∈S, a∈A} where A is any subset of S. All sets in this research are assumed to be finite. Let D be a digraph together with a vertex set V and an arc set E. Let u and v be two different vertices in V and I a nonempty subset of V. The vertices u and v are said to be independent if (u,v)∉E and (v,u)∉E. The set I is called an independent set of D if any two different vertices in I are independent. The independence number of D is the maximum cardinality of an independent set of D. Moreover, the vertices u and v are said to be path independent if there is no dipath from u to v and there is no dipath from v to u. The set I is called a path independent set of D if any two different vertices in I are path independent. The path independence number of D is the maximum cardinality of a path independent set of D. In this research, we describe a lower bound and an upper bound of the independence number of Cayley digraphs of left groups and right groups. Some examples corresponding to those bounds are illustrated here. Furthermore, the exact value of the path independence number of Cayley digraphs of left groups and right groups are also presented.

Keywords: Cayley digraphs, independence number, left groups, path independence number, right groups

Procedia PDF Downloads 138
84 Standard Model-Like Higgs Decay into Displaced Heavy Neutrino Pairs in U(1)' Models

Authors: E. Accomando, L. Delle Rose, S. Moretti, E. Olaiya, C. Shepherd-Themistocleous

Abstract:

Heavy sterile neutrinos are almost ubiquitous in the class of Beyond Standard Model scenarios aimed at addressing the puzzle that emerged from the discovery of neutrino flavour oscillations, hence the need to explain their masses. In particular, they are necessary in a U(1)’ enlarged Standard Model (SM). We show that these heavy neutrinos can be rather long-lived producing distinctive displaced vertices and tracks. Indeed, depending on the actual decay length, they can decay inside a Large Hadron Collider (LHC) detector far from the main interaction point and can be identified in the inner tracking system or the muon chambers, emulated here through the Compact Muon Solenoid (CMS) detector parameters. Among the possible production modes of such heavy neutrino, we focus on their pair production mechanism in the SM Higgs decay, eventually yielding displaced lepton signatures following the heavy neutrino decays into weak gauge bosons. By employing well-established triggers available for the CMS detector and using the data collected by the end of the LHC Run 2, these signatures would prove to be accessible with negligibly small background. Finally, we highlight the importance that the exploitation of new triggers, specifically, displaced tri-lepton ones, could have for this displaced vertex search.

Keywords: beyond the standard model, displaced vertex, Higgs physics, neutrino physics

Procedia PDF Downloads 68
83 Thermal Behaviors of the Strong Form Factors of Charmonium and Charmed Beauty Mesons from Three Point Sum Rules

Authors: E. Yazıcı, H. Sundu, E. Veli Veliev

Abstract:

In order to understand the nature of strong interactions and QCD vacuum, investigation of the meson coupling constants have an important role. The knowledge on the temperature dependence of the form factors is very important for the interpretation of heavy-ion collision experiments. Also, more accurate determination of these coupling constants plays a crucial role in understanding of the hadronic decays. With the increasing of CM energies of the experiments, researches on meson interactions have become one of the more interesting problems of hadronic physics. In this study, we analyze the temperature dependence of the strong form factor of the BcBcJ/ψ vertex using the three point QCD sum rules method. Here, we assume that with replacing the vacuum condensates and also the continuum threshold by their thermal version, the sum rules for the observables remain valid. In calculations, we take into account the additional operators, which appear in the Wilson expansion at finite temperature. We also investigated the momentum dependence of the form factor at T = 0, fit it into an analytic function, and extrapolate into the deep time-like region in order to obtain a strong coupling constant of the vertex. Our results are consistent with the results existing in the literature.

Keywords: QCD sum rules, thermal QCD, heavy mesons, strong coupling constants

Procedia PDF Downloads 108
82 Human Beta Defensin 1 as Potential Antimycobacterial Agent against Active and Dormant Tubercle Bacilli

Authors: Richa Sharma, Uma Nahar, Sadhna Sharma, Indu Verma

Abstract:

Counteracting the deadly pathogen Mycobacterium tuberculosis (M. tb) effectively is still a global challenge. Scrutinizing alternative weapons like antimicrobial peptides to strengthen existing tuberculosis artillery is urgently required. Considering the antimycobacterial potential of Human Beta Defensin 1 (HBD-1) along with isoniazid, the present study was designed to explore the ability of HBD-1 to act against active and dormant M. tb. HBD-1 was screened in silico using antimicrobial peptide prediction servers to identify its short antimicrobial motif. The activity of both HBD-1 and its selected motif (Pep B) was determined at different concentrations against actively growing M. tb in vitro and ex vivo in monocyte derived macrophages (MDMs). Log phase M. tb was grown along with HBD-1 and Pep B for 7 days. M. tb infected MDMs were treated with HBD-1 and Pep B for 72 hours. Thereafter, colony forming unit (CFU) enumeration was performed to determine activity of both peptides against actively growing in vitro and intracellular M. tb. The dormant M. tb models were prepared by following two approaches and treated with different concentrations of HBD-1 and Pep B. Firstly, 20-22 days old M. tbH37Rv was grown in potassium deficient Sauton media for 35 days. The presence of dormant bacilli was confirmed by Nile red staining. Dormant bacilli were further treated with rifampicin, isoniazid, HBD-1 and its motif for 7 days. The effect of both peptides on latent bacilli was assessed by colony forming units (CFU) and most probable number (MPN) enumeration. Secondly, human PBMC granuloma model was prepared by infecting PBMCs seeded on collagen matrix with M. tb(MOI 0.1) for 10 days. Histopathology was done to confirm granuloma formation. The granuloma thus formed was incubated for 72 hours with rifampicin, HBD-1 and Pep B individually. Difference in bacillary load was determined by CFU enumeration. The minimum inhibitory concentrations of HBD-1 and Pep B restricting growth of mycobacteria in vitro were 2μg/ml and 20μg/ml respectively. The intracellular mycobacterial load was reduced significantly by HBD-1 and Pep B at 1μg/ml and 5μg/ml respectively. Nile red positive bacterial population, high MPN/ low CFU count and tolerance to isoniazid, confirmed the formation of potassium deficienybaseddormancy model. HBD-1 (8μg/ml) showed 96% and 99% killing and Pep B (40μg/ml) lowered dormant bacillary load by 68.89% and 92.49% based on CFU and MPN enumeration respectively. Further, H&E stained aggregates of macrophages and lymphocytes, acid fast bacilli surrounded by cellular aggregates and rifampicin resistance, indicated the formation of human granuloma dormancy model. HBD-1 (8μg/ml) led to 81.3% reduction in CFU whereas its motif Pep B (40μg/ml) showed only 54.66% decrease in bacterial load inside granuloma. Thus, the present study indicated that HBD-1 and its motif are effective antimicrobial players against both actively growing and dormant M. tb. They should be further explored to tap their potential to design a powerful weapon for combating tuberculosis.

Keywords: antimicrobial peptides, dormant, human beta defensin 1, tuberculosis

Procedia PDF Downloads 192
81 On the Girth of the Regular Digraph of Ideals of a ‎Commutative ‎Ring

Authors: Masoud Karimi

Abstract:

‎Let R be a commutative ring‎. ‎The regular digraph of ideals of R, which is denoted by‎ Γ(R)‎, ‎is a digraph whose vertex-set is the set of all ‎non-‎trivial ideals of R and‎, ‎for every‎ two distinct vertices I and J‎, ‎there is an arc from I to J‎, ‎whenever I contains‎ a non-zero-divisor on J. In this article, ‎we ‎show ‎that an indecomposable ‎Noetherian ring ‎‎‎R ‎is ‎Artinian ‎local ‎if ‎and ‎only ‎if Z(I)=Z(R) ‎for ‎every ‎non-nilpotent ‎ideal ‎‎‎I‎. ‎Then ‎we ‎conclude ‎that ‎‎the ‎girth ‎of‎ Γ(R)‎ ‎is ‎not ‎equal ‎to ‎four.

Keywords: commutative ring‎, ‎girth‎, regular digraph‎, zero-divisor

Procedia PDF Downloads 187
80 Upper Bounds on the Paired Domination Number of Cubic Graphs

Authors: Bin Sheng, Changhong Lu

Abstract:

Let G be a simple undirected graph with no isolated vertex. A paired dominating set of G is a dominating set which induces a subgraph that has a perfect matching. The paired domination number of G, denoted by γₚᵣ(G), is the size of its smallest paired dominating set. Goddard and Henning conjectured that γₚᵣ(G) ≤ 4n/7 holds for every graph G with δ(G) ≥ 3, except the Petersen Graph. In this paper, we prove this conjecture for cubic graphs.

Keywords: paired dominating set, upper bound, cubic graphs, weight function

Procedia PDF Downloads 68
79 Quality of Service of Transportation Networks: A Hybrid Measurement of Travel Time and Reliability

Authors: Chin-Chia Jane

Abstract:

In a transportation network, travel time refers to the transmission time from source node to destination node, whereas reliability refers to the probability of a successful connection from source node to destination node. With an increasing emphasis on quality of service (QoS), both performance indexes are significant in the design and analysis of transportation systems. In this work, we extend the well-known flow network model for transportation networks so that travel time and reliability are integrated into the QoS measurement simultaneously. In the extended model, in addition to the general arc capacities, each intermediate node has a time weight which is the travel time for per unit of commodity going through the node. Meanwhile, arcs and nodes are treated as binary random variables that switch between operation and failure with associated probabilities. For pre-specified travel time limitation and demand requirement, the QoS of a transportation network is the probability that source can successfully transport the demand requirement to destination while the total transmission time is under the travel time limitation. This work is pioneering, since existing literatures that evaluate travel time reliability via a single optimization path, the proposed QoS focuses the performance of the whole network system. To compute the QoS of transportation networks, we first transfer the extended network model into an equivalent min-cost max-flow network model. In the transferred network, each arc has a new travel time weight which takes value 0. Each intermediate node is replaced by two nodes u and v, and an arc directed from u to v. The newly generated nodes u and v are perfect nodes. The new direct arc has three weights: travel time, capacity, and operation probability. Then the universal set of state vectors is recursively decomposed into disjoint subsets of reliable, unreliable, and stochastic vectors until no stochastic vector is left. The decomposition is made possible by applying existing efficient min-cost max-flow algorithm. Because the reliable subsets are disjoint, QoS can be obtained directly by summing the probabilities of these reliable subsets. Computational experiments are conducted on a benchmark network which has 11 nodes and 21 arcs. Five travel time limitations and five demand requirements are set to compute the QoS value. To make a comparison, we test the exhaustive complete enumeration method. Computational results reveal the proposed algorithm is much more efficient than the complete enumeration method. In this work, a transportation network is analyzed by an extended flow network model where each arc has a fixed capacity, each intermediate node has a time weight, and both arcs and nodes are independent binary random variables. The quality of service of the transportation network is an integration of customer demands, travel time, and the probability of connection. We present a decomposition algorithm to compute the QoS efficiently. Computational experiments conducted on a prototype network show that the proposed algorithm is superior to existing complete enumeration methods.

Keywords: quality of service, reliability, transportation network, travel time

Procedia PDF Downloads 143
78 Hamiltonian Paths and Cycles Passing through Prescribed Edges in the Balanced Hypercubes

Authors: Dongqin Cheng

Abstract:

The n-dimensional balanced hypercube BHn (n ≥ 1) has been proved to be a bipartite graph. Let P be a set of edges whose induced subgraph consists of pairwise vertex-disjoint paths. For any two vertices u, v from different partite sets of V (BHn). In this paper, we prove that if |P| ≤ 2n − 2 and the subgraph induced by P has neither u nor v as internal vertices, or both of u and v as end-vertices, then BHn contains a Hamiltonian path joining u and v passing through P. As a corollary, if |P| ≤ 2n−1, then the BHn contains a Hamiltonian cycle passing through P.

Keywords: interconnection network, balanced hypercube, Hamiltonian cycle, prescribed edges

Procedia PDF Downloads 120
77 Metric Dimension on Line Graph of Honeycomb Networks

Authors: M. Hussain, Aqsa Farooq

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.

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

Procedia PDF Downloads 83
76 An Advanced Approach to Detect and Enumerate Soil-Transmitted Helminth Ova from Wastewater

Authors: Vivek B. Ravindran, Aravind Surapaneni, Rebecca Traub, Sarvesh K. Soni, Andrew S. Ball

Abstract:

Parasitic diseases have a devastating, long-term impact on human health and welfare. More than two billion people are infected with soil-transmitted helminths (STHs), including the roundworms (Ascaris), hookworms (Necator and Ancylostoma) and whipworm (Trichuris) with majority occurring in the tropical and subtropical regions of the world. Despite its low prevalence in developed countries, the removal of STHs from wastewater remains crucial to allow the safe use of sludge or recycled water in agriculture. Conventional methods such as incubation and optical microscopy are cumbersome; consequently, the results drastically vary from person-to-person observing the ova (eggs) under microscope. Although PCR-based methods are an alternative to conventional techniques, it lacks the ability to distinguish between viable and non-viable helminth ova. As a result, wastewater treatment industries are in major need for radically new and innovative tools to detect and quantify STHs eggs with precision, accuracy and being cost-effective. In our study, we focus on the following novel and innovative techniques: -Recombinase polymerase amplification and Surface enhanced Raman spectroscopy (RPA-SERS) based detection of helminth ova. -Use of metal nanoparticles and their relative nanozyme activity. -Colorimetric detection, differentiation and enumeration of genera of helminth ova using hydrolytic enzymes (chitinase and lipase). -Propidium monoazide (PMA)-qPCR to detect viable helminth ova. -Modified assay to recover and enumerate helminth eggs from fresh raw sewage. -Transcriptome analysis of ascaris ova in fresh raw sewage. The aforementioned techniques have the potential to replace current conventional and molecular methods thereby producing a standard protocol for the determination and enumeration of helminth ova in sewage sludge.

Keywords: colorimetry, helminth, PMA-QPCR, nanoparticles, RPA, viable

Procedia PDF Downloads 235
75 Topological Indices of Some Graph Operations

Authors: U. Mary

Abstract:

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 426
74 Sustainable Happiness of Thai People: Monitoring the Thai Happiness Index

Authors: Kalayanee Senasu

Abstract:

This research investigates the influences of different factors on the happiness of Thai people, including both general factors and sustainable ones. Additionally, this study also monitors Thai people’s happiness via Thai Happiness Index developed in 2017. Besides reflecting happiness level of Thai people, this index also identifies related important issues. The data were collected by both secondary related data and primary survey data collected by interviewed questionnaires. The research data were from stratified multi-stage sampling in region, province, district, and enumeration area, and simple random sampling in each enumeration area. The research data cover 20 provinces, including Bangkok and 4-5 provinces in each region of the North, Northeastern, Central, and South. There were 4,960 usable respondents who were at least 15 years old. Statistical analyses included both descriptive and inferential statistics, including hierarchical regression and one-way ANOVA. The Alkire and Foster method was adopted to develop and calculate the Thai happiness index. The results reveal that the quality of household economy plays the most important role in predicting happiness. The results also indicate that quality of family, quality of health, and effectiveness of public administration in the provincial level have positive effects on happiness at about similar levels. For the socio-economic factors, the results reveal that age, education level, and household revenue have significant effects on happiness. For computing Thai happiness index (THaI), the result reveals the 2018 THaI value is 0.556. When people are divided into four groups depending upon their degree of happiness, it is found that a total of 21.1% of population are happy, with 6.0% called deeply happy and 15.1% called extensively happy. A total of 78.9% of population are not-yet-happy, with 31.8% called narrowly happy, and 47.1% called unhappy. A group of happy population reflects the happiness index THaI valued of 0.789, which is much higher than the THaI valued of 0.494 of the not-yet-happy population. Overall Thai people have higher happiness compared to 2017 when the happiness index was 0.506.

Keywords: happiness, quality of life, sustainability, Thai Happiness Index

Procedia PDF Downloads 69
73 Introduction to Transversal Pendant Domination in Graphs

Authors: Nayaka S.R., Putta Swamy, Purushothama S.

Abstract:

Let G=(V, E) be a graph. A dominating set S in G is a pendant dominating set if < S > contains a pendant vertex. A pendant dominating set of G which intersects every minimum pendant dominating set in G is called a transversal pendant dominating set. The minimum cardinality of a transversal pendant dominating set is called the transversal pendant domination number of G, denoted by γ_tp(G). In this paper, we begin to study this parameter. We calculate γ_tp(G) for some families of graphs. Furthermore, some bounds and relations with other domination parameters are obtained for γ_tp(G).

Keywords: dominating set, pendant dominating set, pendant domination number, transversal pendant dominating set, transversal pendant domination number

Procedia PDF Downloads 110