Search Results: 1 - 10 of 100 matches for " "
All listed articles are free for downloading (OA Articles)
Page 1 /100
Display every page Item
Betweenness Centrality in Some Classes of Graphs  [PDF]
Sunil Kumar R,Kannan Balakrishnan,M. Jathavedan
Mathematics , 2014,
Abstract: There are several centrality measures that have been introduced and studied for real world networks. They account for the different vertex characteristics that permit them to be ranked in order of importance in the network. Betweenness centrality is a measure of the influence of a vertex over the flow of information between every pair of vertices under the assumption that information primarily flows over the shortest path between them. In this paper we present betweenness centrality of some important classes of graphs.
Reed's conjecture on some special classes of graphs  [PDF]
Jean-Luc Fouquet,Jean-Marie Vanherpe
Computer Science , 2012,
Abstract: Reed conjectured that for any graph $G$, $\chi(G) \leq \lceil \frac{\omega(G)+\Delta(G)+1}{2}\rceil$, where $\chi(G)$, $\omega(G)$, and $\Delta(G)$ respectively denote the chromatic number, the clique number and the maximum degree of $G$. In this paper, we verify this conjecture for some special classes of graphs, in particular for subclasses of $P_5$-free graphs or $Chair$-free graphs.
Hamiltonian Paths in Some Classes of Grid Graphs
Fatemeh Keshavarz-Kohjerdi,Alireza Bagheri
Journal of Applied Mathematics , 2012, DOI: 10.1155/2012/475087
Abstract: The Hamiltonian path problem for general grid graphs is known to be NP-complete. In this paper, we give necessary and sufficient conditions for the existence of Hamiltonian paths in L-alphabet, C-alphabet, F-alphabet, and E-alphabet grid graphs. We also present linear-time algorithms for finding Hamiltonian paths in these graphs.
Improved upper bounds for the order of some classes of Abelian Cayley and circulant graphs of diameter two  [PDF]
Robert R. Lewis
Mathematics , 2015,
Abstract: In the degree-diameter problem for Abelian Cayley and circulant graphs of diameter 2 and arbitrary degree d there is a wide gap between the best lower and upper bounds valid for all d, being quadratic functions with leading coefficient 1/4 and 1/2 respectively. Recent papers have presented constructions which increase the coefficient of the lower bound to be at or just below 3/8, but only for sparse sets of degree d related to primes of specific congruence classes. By applying results from number theory these constructions can be extended to be valid for every degree above some threshold, establishing an improved asymptotic lower bound approaching 3/8. The constructions use the direct product of the multiplicative and additive subgroups of a Galois field and a specific coprime cyclic group. By generalising this method an improved upper bound, with quadratic coefficient 3/8, is established for this class of construction of Abelian Cayley and circulant graphs. Analysis of the order of the known extremal diameter 2 circulant graphs, up to degree 23, is shown to provide tentative support for a quadratic coefficient of 3/8 for the asymptotic upper bound for the order of general diameter 2 circulant graphs of arbitrary degree.
Some New Classes of Open Distance-Pattern Uniform Graphs  [PDF]
Bibin K. Jose
International Journal of Combinatorics , 2013, DOI: 10.1155/2013/863439
Abstract: Given an arbitrary nonempty subset of vertices in a graph , each vertex in is associated with the set and called its open -distance-pattern. The graph is called open distance-pattern uniform (odpu-) graph if there exists a subset of such that for all and is called an open distance-pattern uniform (odpu-) set of The minimum cardinality of an odpu-set in , if it exists, is called the odpu-number of and is denoted by . Given some property , we establish characterization of odpu-graph with property . In this paper, we characterize odpu-chordal graphs, and thereby characterize interval graphs, split graphs, strongly chordal graphs, maximal outerplanar graphs, and ptolemaic graphs that are odpu-graphs. We also characterize odpu-self-complementary graphs, odpu-distance-hereditary graphs, and odpu-cographs. We prove that the odpu-number of cographs is even and establish that any graph can be embedded into a self-complementary odpu-graph , such that and are induced subgraphs of . We also prove that the odpu-number of a maximal outerplanar graph is either or . 1. Introduction All graphs considered in this paper are finite, simple, undirected, and connected. For graph theoretic terminology, we refer to Harary [1]. The concept of open distance-pattern and open distance-pattern uniform graphs was studied in [2]. Given an arbitrary nonempty subset of vertices in a graph , the open -distance-pattern of a vertex in is defined to be the set , where denotes the distance between the vertices and in . If there exists a nonempty set such that is independent of the choice of , then is called open distance-pattern uniform (odpu-) graph, and the set is called an open distance-pattern uniform (odpu-) set. The minimum cardinality of an odpu-set in , if it exists, is the odpu-number of and is denoted by . In this paper, we characterize several classes of odpu graph such as odpu-chordal graphs, interval graphs, split graphs, strongly chordal graphs, maximal outerplanar graphs, ptolemaic graphs, self-complementary graphs, odpu-distance-hereditary graphs, and odpu-cographs. We need the following definitions and previous results. For a vertex in a connected graph , the eccentricity of is the distance to a vertex farthest from . The minimum eccentricity among the vertices of a connected graph is the radius of , denoted by , and the maximum eccentricity is its diameter, . A vertex in a connected graph is called a central vertex if . The collection of all central vertices is called the center of denoted by . In paper [2], it is proved that a graph with radius is an odpu graph if and
Star edge coloring of some classes of graphs  [PDF]
?udmila Bezegová,Borut Lu?ar,Martina Mockov?iaková,Roman Soták,Riste ?krekovski
Mathematics , 2013, DOI: 10.1002/jgt.21862
Abstract: \textit{A star edge coloring} of a graph is a proper edge coloring without bichromatic paths and cycles of length four. In this paper we establish tight upper bounds for trees and subcubic outerplanar graphs, and derive an upper bound for outerplanar graphs.
Rainbow domination and related problems on some classes of perfect graphs  [PDF]
Wing-Kai Hon,Ton Kloks,Hsian-Hsuan Liu,Hung-Lung Wang
Computer Science , 2015,
Abstract: Let $k \in \mathbb{N}$ and let $G$ be a graph. A function $f: V(G) \rightarrow 2^{[k]}$ is a rainbow function if, for every vertex $x$ with $f(x)=\emptyset$, $f(N(x)) =[k]$. The rainbow domination number $\gamma_{kr}(G)$ is the minimum of $\sum_{x \in V(G)} |f(x)|$ over all rainbow functions. We investigate the rainbow domination problem for some classes of perfect graphs.
On $\mathcal{D}$-equivalence classes of some graphs  [PDF]
Somayeh Jahari,Saeid Alikhani
Mathematics , 2015,
Abstract: Let $G$ be a simple graph of order $n$. The domination polynomial of $G$ is the polynomial $D(G, x)=\sum_{i=1}^n d(G,i) x^i$, where $d(G,i)$ is the number of dominating sets of $G$ of size $i$. The $n$-barbell graph $Bar_n$ with $2n$ vertices, is formed by joining two copies of a complete graph $K_n$ by a single edge. We prove that for every $n\geq 2$, $Bar_n$ is not $\mathcal{D}$-unique, that is, there is another non-isomorphic graph with the same domination polynomial. More precisely, we show that for every $n$, the $\mathcal{D}$-equivalence class of barbell graph, $[Bar_n]$, contains many graphs, which one of them is the complement of book graph of order $n-1$, $B_{n-1}^c$. Also we present many families of graphs in $\mathcal{D}$-equivalence class of $K_{n_1}\cup K_{n_2}\cup \cdots\cup K_{n_k}$.
Some classes of general nonconvex variational inequalities.  [cached]
Muhammad Aslam Noor
Albanian Journal of Mathematics , 2009,
Abstract: In this paper, we introduce and consider a new class of variationalinequalities, which is called the general nonconvex variational inequality. Weestablish the equivalence between the general nonconvex variational inequali-ties and the xed point problems as well as the Wiener-Hopf equations usingthe projection method. This alternative equivalent formulation is used tostudy the existence of a solution of the general convex variational inequalities.We also use this equivalence formulation to suggest some iterative methods.Convergence criteria of these new iterative is also discussed under suitableconditions. Our method of proofs is very simple as compared with other tech-niques.
On the Cluster Size Distribution for Percolation on Some General Graphs  [PDF]
Antar Bandyopadhyay,Jeffrey Steif,Adam Timar
Mathematics , 2008,
Abstract: We show that for any Cayley graph, the probability (at any $p$) that the cluster of the origin has size n decays at a well-defined exponential rate (possibly 0). For general graphs, we relate this rate being positive in the supercritical regime with the amenability/nonamenability of the underlying graph.
Page 1 /100
Display every page Item

Copyright © 2008-2017 Open Access Library. All rights reserved.