Search
Filters
total: 1599
filtered: 1030
displaying 1000 best results Help
Search results for: VERTEX DEGREE
-
A Compact and Lightweight Microwave Tilt Sensor Based on an SRR-Loaded Microstrip Line
PublicationIn this paper, the symmetry property of split ring resonators (SRRs) is exploited to develop a tilt sensor. The sensor is composed of an SRR-loaded microstrip line operating at microwave frequencies. It is shown that the depth of notch in the reflection characteristic of the microstrip is a function of the tilt angle of the SRR. Thus, it can be used for sensing inclination. The sensor benefits from very compact size and light weight....
-
Dynamic F-free Coloring of Graphs
PublicationA problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well...
-
Acoustic Streaming Induced by Periodic and Aperiodic Sound in a Bubbly Liquid
PublicationThe vortex ow which follows intense sound propagating in a bubbly liquid, is considered. The reasons for acoustic streaming are both nonlinearity and dispersion. That makes streaming especial as compared with that in a Newtonian uid. Conclusions concern the vortex ow induced in a half-space by initially harmonic or impulse Gaussian beam. The vortex ow recalls a turbulent ow with increasing in time number of small-scale vortices...
-
On the ratio between 2-domination and total outer-independent domination numbers of trees
PublicationA 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...
-
Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times
PublicationWe consider a generalization of binary search in linear orders to the domain of weighted trees. The goal is to design an adaptive search strategy whose aim is to locate an unknown target vertex of a given tree. Each query to a vertex v incurs a non-negative cost ω(v) (that can be interpreted as the duration of the query) and returns a feedback that either v is the target or the edge incident to v is given that is on the path towards...
-
All graphs with paired-domination number two less than their order
PublicationLet G=(V,E) be a graph with no isolated vertices. A set S⊆V is a paired-dominating set of G if every vertex not in S is adjacent with some vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination number γp(G) of G is defined to be the minimum cardinality of a paired-dominating set of G. Let G be a graph of order n. In [Paired-domination in graphs, Networks 32 (1998), 199-206] Haynes and Slater...
-
An upper bound for the double outer-independent domination number of a tree
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)\D is independent. The double outer-independent domination number of a graph G, denoted by γ_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We prove...
-
The Possibilities of Improving the Fatigue Durabilityof the Ship Propeller Shaft by Burnishing Process
PublicationHeavily loaded structural elements operating in a corrosive environment are usuallyquickly destroyed. An example of such an element is a ship propeller operating in a seawaterenvironment. This research presents a fatigue resistance test performed on elements operating inseawater. Different processing parameters applied on the samples in particular were compared withthe specimens whose surface had been burnished differently and...
-
An Optimized Ka-Band Low Profile Dual-Polarized Transmitarray Antenna With 2D Beam Switching
PublicationThis article presents an optimized dual-polarized transmitarray antenna (TA) designed for MIMO applications at the Ka-band, capable of switching beams in two directions. The antenna aperture uses a small unit cell with three layers of Taconic RF-35 dielectric substrates, which can be easily fabricated using PCB technology. The unit cell achieved a 360-degree phase shift and a transmission magnitude exceeding –0.4 dB at 28 GHz....
-
Unicyclic graphs with equal total and total outer-connected domination numbers
PublicationLet 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...
-
On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublicationIn 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.
-
Ruch wirowy wywoływany przez ultradźwięk w płynach z relaksacją
PublicationRozprawa doktorska poświęcona jest badaniu ruchu wirowego wywoływanego przez ultradźwięk w różnych modelach płynów z relaksacją. Ma ona charakter teoretyczny, jednak wykorzystanie uzyskanych dzięki niej wyników może przynieść lepsze zrozumienie ruchu wirowego wywoływanego przez siłę akustyczną. W I rozdziale rozprawy przedstawione zostały ogólne rozważania dotyczące akustyki nieliniowej. Rozdział II dotyczy ruchu wirowego wywoływanego...
-
3D Hand Shape Modeling for Automatic Assessing Motor Performance in Parkinson's Disease
PublicationIn this paper a method for hand pattern processing to create a 3D hand model is presented. By applying a complete hand armature to the model obtained, an interpolation of three motor tests for an individual Parkinson's disease patient can be performed. To obtain the 3D hand model the top view of the hand from a web cam is analyzed. The hand contour is examined to find characteristic points that allows for dividing hand image into...
-
A lower bound on the double outer-independent domination number of a tree
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)D is independent. The double outer-independent domination number of a graph G, denoted by gamma_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We...
-
The Potential of Greed for Independence
PublicationThe well-known lower bound on the independence number of a graph due to Caro and Wei can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so-called potential functions p(G) : V(G) -> N_0 defined on the vertex set of a graph G for which suitably...
-
Graphs with equal domination and certified domination numbers
PublicationA 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...
-
A novel heterogeneous model of concrete for numerical modelling of ground penetrating radar
PublicationThe ground penetrating radar (GPR) method has increasingly been applied in the non-destructive testing of reinforced concrete structures. The most common approach to the modelling of radar waves is to consider concrete as a homogeneous material. This paper proposes a novel, heterogeneous, numerical model of concrete for exhaustive interpretation of GPR data. An algorithm for determining the substitute values of the material constants...
-
Fast collaborative graph exploration
PublicationWe study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...
-
Fast Collaborative Graph Exploration
PublicationWe study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...
-
New potential functions for greedy independence and coloring
PublicationA potential function $f_G$ of a finite, simple and undirected graph $G=(V,E)$ is an arbitrary function $f_G : V(G) \rightarrow \mathbb{N}_0$ that assigns a nonnegative integer to every vertex of a graph $G$. In this paper we define the iterative process of computing the step potential function $q_G$ such that $q_G(v)\leq d_G(v)$ for all $v\in V(G)$. We use this function in the development of new Caro-Wei-type and Brooks-type...
-
Coronas and Domination Subdivision Number of a Graph
PublicationIn this paper, for a graph G and a family of partitions P of vertex neighborhoods of G, we define the general corona G ◦P of G. Among several properties of this new operation, we focus on application general coronas to a new kind of characterization of trees with the domination subdivision number equal to 3.
-
2-D constitutive equations for orthotropic Cosserat type laminated shells in finite element analysis
PublicationWe propose 2-D Cosserat type orthotropic constitutive equations for laminated shells for the purpose of initial failure estimation in a laminate layer. We use nonlinear 6-parameter shell theory with asymmetric membrane strain measures and Cosserat kinematics as the framework. This theory is specially dedicated to the analysis of irregular shells, inter alia, with orthogonal intersections, since it takes into account the drilling...
-
Turán numbers for odd wheels
PublicationThe Turán number ex(n,G) is the maximum number of edges in any n-vertex graph that does not contain a subgraph isomorphic to G. A wheel W_n is a graph on n vertices obtained from a C_{n−1} by adding one vertex w and making w adjacent to all vertices of the C_{n−1}. We obtain two exact values for small wheels: ex(n,W_5)=\lfloor n^2/4+n/2\rfloor, ex(n,W_7)=\lfloor n^2/4+n/2+1 \rfloor. Given that ex(n,W_6) is already known, this...
-
Weakly connected Roman domination in graphs
PublicationA Roman dominating function on a graph G=(V,E) is defined to be a function f :V → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v)=2. A dominating set D⊆V is a weakly connected dominating set of G if the graph (V,E∩(D×V)) is connected. We define a weakly connected Roman dominating function on a graph G to be a Roman dominating function such that the set...
-
Common Independence in Graphs
PublicationAbstract: 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|...
-
Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationIn this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.
-
Double bondage in graphs
PublicationA 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...
-
Constructing a map of an anonymous graph: applications of universal sequences
PublicationWe study the problem of mapping an unknown environmentrepresented as an unlabelled undirected graph. A robot (or automaton)starting at a single vertex of the graph G has to traverse the graph and return to its starting point building a map of the graph in the process. We are interested in the cost of achieving this task (whenever possible) in terms of the number of edge traversal made by the robot. Another optimization criteria...
-
Cops, a fast robber and defensive domination on interval graphs
PublicationThe game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”,...
-
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationWe consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.
-
Global defensive sets in graphs
PublicationIn the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC ( X ) = true if and only if | N [ X ] ∩ S | ≥ | N [ X ] \ S | holds, where N [ X ] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for...
-
Nondestructive corrosion degradation assessment based on asymmetry of guided wave propagation field
PublicationThe article presents the results of numerical and experimental investigation of guided wave propagation in steel plates subjected to corrosion degradation. The development of novel procedures allowing for the assessment of the corrosion degradation level is crucial in the effective diagnostics of offshore and ship structures that are especially subjected to aggressive environments. The study’s main aim is to investigate the influence...
-
Characteristics of volatile organic compounds emission profiles from hot road bitumens
PublicationA procedure for the investigation and comparison of volatile organic compounds (VOCs) emission profiles to the atmosphere from road bitumens with various degrees of oxidation is proposed. The procedure makes use of headspace analysis and gas chromatography with universal as well as selective detection, including gas chromatography–mass spectrometry (GC–MS). The studies revealed that so-called vacuum residue, which is the main component...
-
A Framework for Searching in Graphs in the Presence of Errors
PublicationWe consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide...
-
Deformable model of a butterfly in motion on the example of Attacus atlas
PublicationInsect wings can undergo significant chordwise (camber) as well as spanwise (twist) deformation during flapping flight but the effect of these deformations is not well understood. The shape and size of butterfly wings leads to particularly large wing deformations, making them an ideal test case for investigation of these effects. High-speed videogrammetry was used to capture the wing kinematics and deformations. The movements of...
-
The Education of Analytical Chemists in Polish Universities
PublicationAnalytical Chemistry plays a very important role in the modern world. The main reasons are; the need of environmental monitoring, quality of food and water control, human health, quality of industrial production control, nanotechnologies and material science. Together with Inorganic Chemistry, Organic Chemistry and Physical Chemistry, Analytical Chemistry is a fundamental chemical course. The education of Analytical Chemists is...
-
Assessment of the Relationship between the Shape of the Lateral Meniscus and the Risk of Extrusion Based on MRI Examination of the Knee Joint
PublicationBackground Meniscus extrusion is a serious and relatively frequent clinical problem. For this reason the role of different risk factors for this pathology is still the subject of debate. The goal of this study was to verify the results of previous theoretical work, based on the mathematical models, regarding a relationship between the cross-section shape of the meniscus and the risk of its extrusion. Materials and Methods Knee...
-
Brushing with additional cleaning restrictions
PublicationIn 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...
-
Reconfiguring Minimum Dominating Sets in Trees
PublicationWe provide tight bounds on the diameter of γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. In particular, we prove that for any tree T of order n ≥ 3, the diameter of its γ-graph is at most n/2 in the single vertex replacement adjacency model, whereas in the slide adjacency model, it is at most 2(n − 1)/3. Our proof is constructive, leading to a simple linear-time algorithm for determining...
-
Certified domination
PublicationImagine that we are given a set D of officials and a set W of civils. For each civil x ∈ W, there must be an official v ∈ D that can serve x, and whenever any such v is serving x, there must also be another civil w ∈ W that observes v, that is, w may act as a kind of witness, to avoid any abuse from v. What is the minimum number of officials to guarantee such a service, assuming a given social network? In this paper, we introduce...
-
Secure Italian domination in graphs
PublicationAn 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...
-
Application of Monte-Carlo method to modelling influence of selected soil heterogeneity on macrodispersion of pollutants in unsaturated soil medium
PublicationThe influence of soil heterogeneity on miscible solute transport in soil is analyzed. The transport process is simulated numerically using the Monte-Carlo method. This paper shows how different types of soil heterogeneity influence the process of contaminant spreading. If independent flow paths exist in the soil, the degree of the mixing of pollutants in the outflow from the soil profile is larger. If the preferential flow paths...
-
Path components of the space of gradient vector fields on the two dimensional disc
PublicationWe present a short proof that if two gradient maps on the twodimensional disc have the same degree, then they are gradient homotopic.
-
On trees with equal 2-domination and 2-outer-independent domination numbers
PublicationFor 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...
-
A lower bound on the total outer-independent domination number of a tree
PublicationA 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 total outer-independent domination number of a graph G, denoted by gamma_t^{oi}(G), is the minimum cardinality of a total outer-independent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have gamma_t^{oi}(T) >= (2n-2l+2)/3,...
-
Evaluation of Pavement Temperatures in Poland During Winter Conditions
PublicationThe paper presents the analysis of pavement temperatures from meteorological stations located at the Polish national roads during the impact of low winter temperatures. Presented issue is particularly important in view of the problem of low-temperature cracks that occur in the asphalt pavement under the influence of low temperatures. For each location of meteorological station there were analysed measurements of the temperature...
-
Hardware cryptography coprocessor for system on chip soft processor
PublicationW artykule przedstawiono realizację sprzętową i programową szyfrującejo i deszyfrującego algorytmu AES.Obydwie implementacje zostały zralizowane z wykorzystaniem układu Virtex II i przetestowane. Jako kryterium porónawcze wybrano zużycie zasobów układu oraz wydajność. Realizacja sprzętowa wykonuje operację szyfrowania 2 dekady szybcie niż wersja programowa, ale wymaga pięciokrotnie więcej zasobówIn this paper hardware and software...
-
Vegetable derived-oil facilitating carbon black migration from waste tire rubbers and its reinforcement effect
PublicationThree dimensional chemically cross-linked polymer networks present a great challenge for recycling and reutilization of waste tire rubber. In this work, the covalently cross-linked networks of ground tire rubber (GTR) were degraded heterogeneously under 150 °C due to the synergistic effects of the soybean oil and controlled oxidation. The degradation mechanism was discussed using Horikx theory and Fourier transformation infrared...
-
Spectroscopic studies of Nb-doped tricalcium phosphate glass-ceramics prepared by sol-gel method
PublicationCalcium-phosphate based glasses and glass-ceramics play a crucial role in the tissue engineering development. Apart from their high biocompatibility and excellent ability to undergo varying degrees of resorbability1, they exhibit relatively high bioactivity and due to that they are commonly used as bone and dental implants. A substantial research effort is devoted to improve calcium-phosphate materials physico-chemical properties...
-
Some variations of perfect graphs
PublicationWe consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) =γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k -path vertex cover number and the distance (k−1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k≥2. Moreover, we provide a complete characterisation of (ψ2−γ1)-perfect graphs describing the set of its forbidden induced subgraphs and providing...