Search results for: DISTANCE K -DOMINATION NUMBER - Bridge of Knowledge

Search

Search results for: DISTANCE K -DOMINATION NUMBER

Filters

total: 315
filtered: 217

clear all filters


Chosen catalog filters

  • Category

  • Year

  • Options

clear Chosen catalog filters disabled

Search results for: DISTANCE K -DOMINATION NUMBER

  • 2-outer-independent domination in graphs

    Publication

    We initiate the study of 2-outer-independent domination in graphs. A 2-outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)\D has at least two neighbors in D, and the set V(G)\D is independent. The 2-outer-independent domination number of a graph G is the minimum cardinality of a 2-outer-independent dominating set of G. We show that if a graph has minimum degree at least two,...

    Full text available to download

  • Bondage number of grid graphs

    Publication

    The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. Here we study the bondage number of some grid-like graphs. In this sense, we obtain some bounds or exact values of the bondage number of some strong product and direct product of two paths.

    Full text available to download

  • Graphs with equal domination and certified domination numbers

    Publication

    - Opuscula Mathematica - Year 2019

    A setDof vertices of a graphG= (VG,EG) is a dominating set ofGif every vertexinVG−Dis adjacent to at least one vertex inD. The domination number (upper dominationnumber, respectively) ofG, denoted byγ(G) (Γ(G), respectively), is the cardinality ofa smallest (largest minimal, respectively) dominating set ofG. A subsetD⊆VGis calleda certified dominating set ofGifDis a dominating set ofGand every vertex inDhas eitherzero...

    Full text available to download

  • Total Domination Versus Domination in Cubic Graphs

    Publication

    A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...

    Full text available to download

  • Unicyclic graphs with equal total and total outer-connected domination numbers

    Publication

    - ARS COMBINATORIA - Year 2015

    Let G = (V,E) be a graph without an isolated vertex. A set D ⊆ V (G) is a total dominating set if D is dominating and the in- duced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total domi- nating set of G. A set D ⊆ V (G) is a total outer–connected dominating set if D is total dominating and the induced subgraph G[V (G)−D] is a connected graph. The total outer–connected...

    Full text to download in external service

  • Independent Domination Subdivision in Graphs

    Publication

    - GRAPHS AND COMBINATORICS - Year 2021

    A set $S$ of vertices in a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in~$S$. If, in addition, $S$ is an independent set, then $S$ is an independent dominating set. The independent domination number $i(G)$ of $G$ is the minimum cardinality of an independent dominating set in $G$. The independent domination subdivision number $\sdi(G)$ is the minimum number of edges that must be subdivided (each...

    Full text available to download

  • On trees with equal domination and total outer-independent domination numbers

    Publication

    For a graph G=(V,E), a subset D subseteq V(G) is a dominating set if every vertex of V(G)D has a neighbor in D, while it is a total outer-independent dominating set if every vertex of G has a neighbor in D, and the set V(G)D is independent. The domination (total outer-independent domination, respectively) number of G is the minimum cardinality of a dominating (total outer-independent dominating, respectively) set of G. We characterize...

  • On trees with equal 2-domination and 2-outer-independent domination numbers

    For a graph G = (V,E), a subset D \subseteq V(G) is a 2-dominating set if every vertex of V(G)\D$ has at least two neighbors in D, while it is a 2-outer-independent dominating set if additionally the set V(G)\D is independent. The 2-domination (2-outer-independent domination, respectively) number of G, is the minimum cardinality of a 2-dominating (2-outer-independent dominating, respectively) set of G. We characterize all trees...

    Full text available to download

  • On the ratio between 2-domination and total outer-independent domination numbers of trees

    A 2-dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)D has a at least two neighbors in D. A total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V(G)D is independent. The 2-domination (total outer-independent domination, respectively) number of a graph G is the minimum cardinality of a 2-dominating (total...

    Full text to download in external service

  • Weakly convex and convex domination numbers of some products of graphs

    If $G=(V,E)$ is a simple connected graph and $a,b\in V$, then a shortest $(a-b)$ path is called a $(u-v)$-{\it geodesic}. A set $X\subseteq V$ is called {\it weakly convex} in $G$ if for every two vertices $a,b\in X$ exists $(a-b)$- geodesic whose all vertices belong to $X$. A set $X$ is {\it convex} in $G$ if for every $a,b\in X$ all vertices from every $(a-b)$-geodesic belong to $X$. The {\it weakly convex domination number}...

  • Super Dominating Sets in Graphs

    Publication

    In this paper some results on the super domination number are obtained. We prove that if T is a tree with at least three vertices, then n2≤γsp(T)≤n−s, where s is the number of support vertices in T and we characterize the extremal trees.

    Full text to download in external service

  • On some Zarankiewicz numbers and bipartite Ramsey Numbers for Quadrilateral

    Publication

    - ARS COMBINATORIA - Year 2015

    The Zarankiewicz number z ( m, n ; s, t ) is the maximum number of edges in a subgraph of K m,n that does not contain K s,t as a subgraph. The bipartite Ramsey number b ( n 1 , · · · , n k ) is the least positive integer b such that any coloring of the edges of K b,b with k colors will result in a monochromatic copy of K n i ,n i in the i -th color, for some i , 1 ≤ i ≤ k . If n i = m for all i , then we denote this number by b k ( m )....

    Full text available to download

  • On extremal sizes of locally k-tree graphs

    Publication

    - CZECHOSLOVAK MATHEMATICAL JOURNAL - Year 2010

    A graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k>=0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k >= 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the...

    Full text to download in external service

  • Numerical modeling of exciton impact in two crystalographic phases of the organo-lead halide perovskite (CH3NH3PbI3) solar cell

    To improve the power conversion efficiency of solar cells based on organo–lead halide perovskites, a detailed understanding of the device physics is fundamental. Here, a computational analysis of excitons impact is reported for these types of photocell. Numerical calculations based on the model, which take into account electronic charge carriers (electrons and holes), excitons and ions, have been carried out. The role of excitons...

    Full text available to download

  • Turbulence model evaluation for numerical modelling of turbulent flow and heat transfer of nanofluids

    Publication

    - Applied Mechanics and Materials - Year 2016

    In this work, Nusselt number and friction factor are calculated numerically for turbulent pipe flow (Reynolds number between 6000 and 12000) with constant heat flux boundary condition using nanofluids. The nanofluid is modelled with the single-phase approach and the simulation results are compared with experimental data. Ethylene glycol and water, 60:40 EG/W mass ratio, as base fluid and SiO2 nanoparticles are used as nanofluid...

  • A Study on Influence of Normalization Methods on Music Genre Classification Results Employing kNN Algorithms

    This paper presents a comparison of different normalization methods applied to the set of feature vectors of music pieces. Test results show the influence of min-nlax and Zero-Mean normalization methods, employing different distance functions (Euclidean, Manhattan, Chebyshev, Minkowski) as a pre-processing for genre classification, on k-Nearest Neighbor (kNN) algorithm classification results.

    Full text available to download

  • Minimum order of graphs with given coloring parameters

    Publication

    - DISCRETE MATHEMATICS - Year 2015

    A complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),...

    Full text available to download

  • Bipartite theory of graphs: outer-independent domination

    Publication

    - NATIONAL ACADEMY SCIENCE LETTERS-INDIA - Year 2015

    Let $G = (V,E)$ be a bipartite graph with partite sets $X$ and $Y$. Two vertices of $X$ are $X$-adjacent if they have a common neighbor in $Y$, and they are $X$-independent otherwise. A subset $D \subseteq X$ is an $X$-outer-independent dominating set of $G$ if every vertex of $X \setminus D$ has an $X$-neighbor in $D$, and all vertices of $X \setminus D$ are pairwise $X$-independent. The $X$-outer-independent domination number...

    Full text to download in external service

  • On Computational Aspects of Greedy Partitioning of Graphs

    Publication

    - Year 2017

    In this paper we consider a problem of graph P-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a P-coloring with a least k colors is NP-complete for an infinite...

    Full text to download in external service

  • Computational aspects of greedy partitioning of graphs

    In this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...

    Full text available to download

  • Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring

    A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas...

    Full text available to download

  • Secure Italian domination in graphs

    Publication

    - JOURNAL OF COMBINATORIAL OPTIMIZATION - Year 2021

    An Italian dominating function (IDF) on a graph G is a function f:V(G)→{0,1,2} such that for every vertex v with f(v)=0, the total weight of f assigned to the neighbours of v is at least two, i.e., ∑u∈NG(v)f(u)≥2. For any function f:V(G)→{0,1,2} and any pair of adjacent vertices with f(v)=0 and u with f(u)>0, the function fu→v is defined by fu→v(v)=1, fu→v(u)=f(u)−1 and fu→v(x)=f(x) whenever x∈V(G)∖{u,v}. A secure Italian dominating...

    Full text available to download

  • 2-bondage in graphs

    A 2-dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. The 2-bondage number of G, denoted by b_2(G), is the minimum cardinality among all sets of edges E' subseteq E such that gamma_2(G-E') > gamma_2(G). If for every E' subseteq E we have...

    Full text to download in external service

  • Common Independence in Graphs

    Publication

    - Symmetry-Basel - Year 2021

    Abstract: The cardinality of a largest independent set of G, denoted by α(G), is called the independence number of G. The independent domination number i(G) of a graph G is the cardinality of a smallest independent dominating set of G. We introduce the concept of the common independence number of a graph G, denoted by αc(G), as the greatest integer r such that every vertex of G belongs to some independent subset X of VG with |X|...

    Full text available to download

  • Bounds on the Cover Time of Parallel Rotor Walks

    Publication

    - Year 2014

    The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node maintains a cyclic ordering of its outgoing arcs, and successively propagates walkers which visit it along its outgoing arcs in...

    Full text to download in external service

  • Equitable coloring of hypergraphs

    Publication

    - DISCRETE APPLIED MATHEMATICS - Year 2019

    A hypergraph is equitablyk-colorable if its vertices can be partitioned into k sets/colorclasses in such a way that monochromatic edges are avoided and the number of verticesin any two color classes differs by at most one. We prove that the problem of equitable 2-coloring of hypergraphs is NP-complete even for 3-uniform hyperstars. Finally, we apply the method of dynamic programming for designing a polynomial-time algorithm to...

    Full text available to download

  • The complexity of minimum-length path decompositions

    Publication

    - JOURNAL OF COMPUTER AND SYSTEM SCIENCES - Year 2015

    We consider a bi-criteria generalization of the pathwidth problem, where, for given integers k, l and a graph G, we ask whether there exists a path decomposition P of G such that the width of P is at most k and the number of bags in P, i.e., the length of P, is at most l. We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter...

    Full text available to download

  • New Method for Increasing Precision of Position Estimation of a Moving Person in Hybrid Inertial Navigation System

    Publication

    In this article a new method for increasing precision of position estimation of inertial navigation in hybrid localization system with reduced number of reference nodes for radio distance measurements is presented. Measuring tests were carried out to verify precision of position estimation of moving person in indoor environment.

  • Towards a classification of networks with asymmetric inputs

    Publication

    - NONLINEARITY - Year 2021

    Coupled cell systems associated with a coupled cell network are determined by (smooth) vector fields that are consistent with the network structure. Here, we follow the formalisms of Stewart et al (2003 SIAM J. Appl. Dyn. Syst. 2, 609–646), Golubitsky et al (2005 SIAM J. Appl. Dyn. Syst. 4, 78–100) and Field (2004 Dyn. Syst. 19, 217–243). It is known that two non-isomorphic n-cell coupled networks can determine the same sets of...

    Full text available to download

  • Spatial pattern of ASG-EUPOS sites

    Publication

    - Open Geosciences - Year 2017

    The article presents the spatial pattern analysis of the ASG-EUPOS permanent GNSS stations in Poland. Using different methods and tools (nearest neighbour, Riplay’s K-function, morphology of Thiessen polygons) we proved that the station distribution model changes within scales. At short distances up to 65 km, which are typical lengths in the network, stations are irregularly dispersed. Increasing this distance to 130 km and over...

    Full text available to download

  • New Method for Increasing Precision of Position Estimation in Hybrid Inertial Navigation System

    In article new method for increasing precision of position estimation by using inertial navigation in hybrid localization system with reduced number of reference nodes for radio distance measurements was presented. Measuring campaign using developed measuring stand were carried out to verify precision of position estimation of moving person in indoor environment.

  • Double bondage in graphs

    Publication

    A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G, denoted by gamma_d(G), is the minimum cardinality of a double dominating set of G. The double bondage number of G, denoted by b_d(G), is the minimum cardinality among all sets...

    Full text to download in external service

  • On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs

    In the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.

    Full text available to download

  • 2-Coloring number revisited

    2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow...

    Full text available to download

  • Evaluation the P-Delta Effect on Collapse Capacity of Adjacent Structures Subjected to Far-field Ground Motions

    Publication

    - Civil Engineering Journal-Tehran - Year 2018

    In urban areas, adjacent structures can be seen in any insufficient distance from each other, because of economic reasons ‎and refusal of acquired minimum separation distance according to seismic previsions. Collapse capacity assessment of ‎structures is one of the important objectives of performance-based seismic engineering. The purpose of this study is to ‎consider the pounding phenomenon and P-Delta effect in seismic collapse...

    Full text available to download

  • Earthquake–induced pounding on response of adjacent structures in series: experimental and numerical study

    Publication

    - Year 2015

    Pounding between structures in series during earthquakes may cause serious damage in the structur-al elements. The aim of this paper is to show the results of an experimental and numerical study that is focused on pounding between more than two structures which may be called "structures in series". In this study, the shaking table experiments, as well as the numerical analyses, were performed using three tower models including...

  • Non-isolating bondage in graphs

    A dominating set of a graph $G = (V,E)$ is a set $D$ of vertices of $G$ such that every vertex of $V(G) \setminus D$ has a neighbor in $D$. The domination number of a graph $G$, denoted by $\gamma(G)$, is the minimum cardinality of a dominating set of $G$. The non-isolating bondage number of $G$, denoted by $b'(G)$, is the minimum cardinality among all sets of edges $E' \subseteq E$ such that $\delta(G-E') \ge 1$ and $\gamma(G-E')...

    Full text available to download

  • Non-isolating 2-bondage in graphs

    A 2-dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. The non-isolating 2-bondage number of G, denoted by b_2'(G), is the minimum cardinality among all sets of edges E' subseteq E such that delta(G-E') >= 1 and gamma_2(G-E') > gamma_2(G)....

    Full text available to download

  • Steady magnetohydrodynamic flow in a diverging channel with suction or blowing

    Publication

    - ZEITSCHRIFT FUR ANGEWANDTE MATHEMATIK UND PHYSIK - Year 2013

    An analysis is made of steady two-dimensional divergent flow of an electrically conducting incompressible viscous fluid in a channel formed by two non-parallel walls, the flow being caused by a source of fluid volume at the intersection of the walls. The fluid is permeated by a magnetic field produced by an electric current along the line of intersection of the channel walls. The walls are porous and subjected to either suction...

    Full text to download in external service

  • Examining Impact of Speed Recommendation Algorithm Operating in Autonomous Road Signs on Minimum Distance between Vehicles

    Publication

    - Remote Sensing - Year 2022

    An approach to a new kind of recommendation system design that suggests safe speed on the road is presented. Real data obtained on roads were used for the simulations. As part of a project related to autonomous road sign development, a number of measurements were carried out on both local roads and expressways. A speed recommendation model was created based on gathered traffic data employing the traffic simulator. Depending on...

    Full text available to download

  • Optimal backbone coloring of split graphs with matching backbones

    For a graph G with a given subgraph H, the backbone coloring is defined as the mapping c: V(G) -> N+ such that |c(u)-c(v)| >= 2 for each edge uv \in E(H) and |c(u)-c(v)| >= 1 for each edge uv \in E(G). The backbone chromatic number BBC(G;H) is the smallest integer k such that there exists a backbone coloring with max c(V(G)) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.

    Full text available to download

  • Verification of Formulas for Periods of Adjacent Buildings Used to Assess Minimum Separation Gap Preventing Structural Pounding during Earthquakes

    Publication

    - Advances in Civil Engineering - Year 2019

    Insufficient separation distance between adjacent buildings may lead to serious damages during earthquakes due to structural pounding. The best way to prevent collisions is to provide sufficiently large separation distance between the structures. In this paper, the periods of two closely-spaced linear and nonlinear buildings have been investigated so as to accurately assess the minimum in-between separation gap. A new equation...

    Full text available to download

  • Brushing with additional cleaning restrictions

    Publication

    In graph cleaning problems, brushes clean a graph by traversing it subject to certain rules. We consider the process where at each time step, a vertex that has at least as many brushes as incident, contaminated edges, sends brushes down these edges to clean them. Various problems arise, such as determining the minimum number of brushes (called the brush number) that are required to clean the entire graph. Here, we study a new variant...

    Full text available to download

  • Bounds on the cover time of parallel rotor walks

    Publication

    - JOURNAL OF COMPUTER AND SYSTEM SCIENCES - Year 2016

    The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider...

    Full text available to download

  • Parallel Computations of Text Similarities for Categorization Task

    Publication

    - Year 2013

    In this chapter we describe the approach to parallel implementation of similarities in high dimensional spaces. The similarities computation have been used for textual data categorization. A test datasets we create from Wikipedia articles that with their hyper references formed a graph used in our experiments. The similarities based on Euclidean distance and Cosine measure have been used to process the data using k-means algorithm....

  • Dynamic coloring of graphs

    Publication

    - FUNDAMENTA INFORMATICAE - Year 2012

    Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In...

  • The computational complexity of the backbone coloring problem for planar graphs with connected backbones

    In the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...

    Full text available to download

  • Influence of accelerometer signal pre-processing and classification method on human activity recognition

    A study of data pre-processing influence on accelerometer-based human activity recognition algorithms is presented. The frequency band used to filter-out the accelerometer signals and the number of accelerometers involved were considered in terms of their influence on the recognition accuracy. In the test four methods of classification were used: support vector machine, decision trees, neural network, k-nearest neighbor.

    Full text to download in external service

  • Pedestrian Safety in Road Traffic in Poland

    Every third road accident in Poland involves a pedestrian as a participant or, most of the time, a casualty. Pedestrian accidents are usually the result of complex situations and the outcome of a number of factors related to driver and pedestrian behaviour and road infrastructure. Safety depends largely on how well the traffic condition is perceived and on visibility in traffic. The paper presents the results of analyses of methodologies...

    Full text available to download

  • Investigations of Aerodynamics of Tesla Bladeless Microturbines

    Publication
    • Ł. Jędrzejewski
    • P. Lampart

    - Journal of Theoretical and Applied Mechanics - Year 2011

    The paper presents an analysis of a Tesla bladeless turbine for a co-generating micro-power plant of heat capacity 20 kW, whichoperates in an organic Rankine cycle with a low-boiling medium. Numerical calculations of flow in several Tesla turbine models areperformed for a range of design parameters. Results of investigations exhibit interesting features in the distribution of flowparameters within the turbine interdisk space. The...

    Full text available to download