Search results for "indifference."
showing 10 items of 18 documents
Neighbor-Distinguishing k-tuple Edge-Colorings of Graphs
2009
AbstractThis paper studies proper k-tuple edge-colorings of graphs that distinguish neighboring vertices by their sets of colors. Minimum numbers of colors for such colorings are determined for cycles, complete graphs and complete bipartite graphs. A variation in which the color sets assigned to edges have to form cyclic intervals is also studied and similar results are given.
On the chromatic number of disk graphs
1998
Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their different generalizations. For all these graphs including the most general class of the double disk (DD) graphs, it is shown that X(G) ≤ c.ω(G) for a constant c. Several coloring algorithms are analyzed for disk graphs, aiming to improve the bounds on X(G). We find that their worst-case performance expressed in the number of used colors is indeed reached in some instances.
On the imprecision of consumer's spatial preferences
1978
Faced with a set of needs of different intensities and which he perceives more or less indistinctly, a consumer is not normally capable of selecting among the elements belonging to his set of possible consumptions, those he prefers or is indifferent to and those from which he is likely to derive utility. Moreover the goods and services are attainable to different degrees (available in supply space) and his knowledge is perfect only in border-line cases with the result that his world is generally imprecise. Even someone with an exceptional gift for discrimination is not capable of formulating for any pair of goods, his preference or indifference according to binary logic. The purpose of this…
Guises and their Existence
1996
According to H-N. Castafieda, a guise the very thin individual which lies at the bottom of the ontological furniture of the world is indifferent to existence in a Meinongian way, in the sense that it remains the same whether it exists or not. Moreover, its existence does not alter its intentional character, as it is the very same individual which is thought of regardless of its being real or not. ~ In what follows, I will attempt to show that with regards to guises both theses are illegitimate, unless one introduces the notion of an existentiallyconditioned property as a counterfactual property which a guise has prior to its actual existence. To do so means to work out an amendment to Casta…
On Sturmian Graphs
2007
AbstractIn this paper we define Sturmian graphs and we prove that all of them have a certain “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones.
Some properties of vertex-oblique graphs
2016
The type t G ( v ) of a vertex v ? V ( G ) is the ordered degree-sequence ( d 1 , ? , d d G ( v ) ) of the vertices adjacent with v , where d 1 ? ? ? d d G ( v ) . A graph G is called vertex-oblique if it contains no two vertices of the same type. In this paper we show that for reals a , b the class of vertex-oblique graphs G for which | E ( G ) | ? a | V ( G ) | + b holds is finite when a ? 1 and infinite when a ? 2 . Apart from one missing interval, it solves the following problem posed by Schreyer et?al. (2007): How many graphs of bounded average degree are vertex-oblique? Furthermore we obtain the tight upper bound on the independence and clique numbers of vertex-oblique graphs as a fun…
On Coloring Unit Disk Graphs
1998
In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.
On the hardness of optimization in power-law graphs
2008
Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y"i of a given degree i is proportional to i^-^@b where @b>0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent @b? Our main result is the proof that many classical NP-hard graph-theoretic optimizati…
Serving God in a largely theocratic society: rivalry and cooperation between Church and King
2009
Theocracy may be understood in different ways. The meaning mostly used is government by priesthood but we may call that “ecclesiocracy” or “hierocracy.” Here, theocracy will designate government according to God’s prescriptions and wishes—with the specification that the implementation or satisfaction of these prescriptions and wishes should be a public or political rather than a private affair and should involve some degree of coercion. The two meanings are different notably because, in the second, priests need not be the ones, or the only ones, who rule on God’s behalf.
Radio Labelings of Distance Graphs
2013
A radio $k$-labeling of a connected graph $G$ is an assignment $c$ of non negative integers to the vertices of $G$ such that $$|c(x) - c(y)| \geq k+1 - d(x,y),$$ for any two vertices $x$ and $y$, $x\ne y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio labelings of distance graphs, i.e., graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in D$.